Wiggle Sort Linked List
MediumUpdated: Oct 13, 2025
Problem
Given a linked list, rearrange the node values such that they appear in alternating low -> high -> low -> high ... form.
Examples
Example 1
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 3 -> 2 -> 5 -> 4
Explanation: The values alternate between low and high: 1 < 3 > 2 < 5 > 4
Example 2
Input: 5 -> 4 -> 3 -> 2 -> 1
Output: 4 -> 5 -> 2 -> 3 -> 1
Explanation: After rearranging: 4 < 5 > 2 < 3 > 1
Example 3
Input: 1
Output: 1
Explanation: Single node remains unchanged
Example 4
Input: 3 -> 1
Output: 1 -> 3
Explanation: Ensure first position has smaller value: 1 < 3
Solution
Method 1 - In-Place Value Swapping
Intuition
We can achieve the wiggle pattern by traversing the linked list and ensuring that at even positions (0, 2, 4...) we have smaller values than the next position, and at odd positions (1, 3, 5...) we have larger values than the next position. If this condition is violated, we simply swap the values.
Approach
- Start from the head of the linked list
- Traverse the list with a position counter
- For even positions (i % 2 == 0): ensure current value < next value
- For odd positions (i % 2 == 1): ensure current value > next value
- If the condition is violated, swap the current and next node values
- Continue until we reach the end of the list
- Return the modified linked list
Code
C++
class Solution {
public:
ListNode* wiggleSort(ListNode* head) {
if (!head || !head->next) return head;
ListNode* curr = head;
int pos = 0;
while (curr && curr->next) {
if (pos % 2 == 0) {
// Even position: should be smaller than next
if (curr->val > curr->next->val) {
swap(curr->val, curr->next->val);
}
} else {
// Odd position: should be larger than next
if (curr->val < curr->next->val) {
swap(curr->val, curr->next->val);
}
}
curr = curr->next;
pos++;
}
return head;
}
};
Go
func wiggleSort(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
curr := head
pos := 0
for curr != nil && curr.Next != nil {
if pos%2 == 0 {
// Even position: should be smaller than next
if curr.Val > curr.Next.Val {
curr.Val, curr.Next.Val = curr.Next.Val, curr.Val
}
} else {
// Odd position: should be larger than next
if curr.Val < curr.Next.Val {
curr.Val, curr.Next.Val = curr.Next.Val, curr.Val
}
}
curr = curr.Next
pos++
}
return head
}
Java
class Solution {
public ListNode wiggleSort(ListNode head) {
if (head == null || head.next == null) return head;
ListNode curr = head;
int pos = 0;
while (curr != null && curr.next != null) {
if (pos % 2 == 0) {
// Even position: should be smaller than next
if (curr.val > curr.next.val) {
int temp = curr.val;
curr.val = curr.next.val;
curr.next.val = temp;
}
} else {
// Odd position: should be larger than next
if (curr.val < curr.next.val) {
int temp = curr.val;
curr.val = curr.next.val;
curr.next.val = temp;
}
}
curr = curr.next;
pos++;
}
return head;
}
}
Kotlin
class Solution {
fun wiggleSort(head: ListNode?): ListNode? {
if (head?.next == null) return head
var curr = head
var pos = 0
while (curr?.next != null) {
if (pos % 2 == 0) {
// Even position: should be smaller than next
if (curr.`val` > curr.next!!.`val`) {
val temp = curr.`val`
curr.`val` = curr.next!!.`val`
curr.next!!.`val` = temp
}
} else {
// Odd position: should be larger than next
if (curr.`val` < curr.next!!.`val`) {
val temp = curr.`val`
curr.`val` = curr.next!!.`val`
curr.next!!.`val` = temp
}
}
curr = curr.next
pos++
}
return head
}
}
Python
class Solution:
def wiggleSort(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
curr = head
pos = 0
while curr and curr.next:
if pos % 2 == 0:
# Even position: should be smaller than next
if curr.val > curr.next.val:
curr.val, curr.next.val = curr.next.val, curr.val
else:
# Odd position: should be larger than next
if curr.val < curr.next.val:
curr.val, curr.next.val = curr.next.val, curr.val
curr = curr.next
pos += 1
return head
Rust
impl Solution {
pub fn wiggle_sort(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
if head.is_none() || head.as_ref().unwrap().next.is_none() {
return head;
}
let mut head = head;
let mut curr = head.as_mut();
let mut pos = 0;
while let Some(node) = curr {
if let Some(next_node) = &mut node.next {
if pos % 2 == 0 {
// Even position: should be smaller than next
if node.val > next_node.val {
let temp = node.val;
node.val = next_node.val;
next_node.val = temp;
}
} else {
// Odd position: should be larger than next
if node.val < next_node.val {
let temp = node.val;
node.val = next_node.val;
next_node.val = temp;
}
}
curr = node.next.as_mut();
pos += 1;
} else {
break;
}
}
head
}
}
TypeScript
class Solution {
wiggleSort(head: ListNode | null): ListNode | null {
if (!head || !head.next) return head;
let curr: ListNode | null = head;
let pos = 0;
while (curr && curr.next) {
if (pos % 2 === 0) {
// Even position: should be smaller than next
if (curr.val > curr.next.val) {
[curr.val, curr.next.val] = [curr.next.val, curr.val];
}
} else {
// Odd position: should be larger than next
if (curr.val < curr.next.val) {
[curr.val, curr.next.val] = [curr.next.val, curr.val];
}
}
curr = curr.next;
pos++;
}
return head;
}
}
Complexity
- ⏰ Time complexity:
O(n), where n is the number of nodes in the linked list. We traverse the list exactly once - 🧺 Space complexity:
O(1), as we only use a constant amount of extra space for variables
Method 2 - Sort and Rearrange
Intuition
Another approach is to first extract all values from the linked list, sort them, and then rearrange them in a wiggle pattern. We place smaller values at even positions and larger values at odd positions alternately.
Approach
- Traverse the linked list and collect all values in an array
- Sort the array of values
- Create the wiggle pattern by:
- Placing values at even indices of sorted array at positions 0, 2, 4...
- Placing values at odd indices of sorted array at positions 1, 3, 5...
- Update the linked list nodes with the rearranged values
- Return the modified linked list
Code
C++
class Solution {
public:
ListNode* wiggleSort(ListNode* head) {
if (!head || !head->next) return head;
vector<int> vals;
ListNode* curr = head;
// Collect all values
while (curr) {
vals.push_back(curr->val);
curr = curr->next;
}
// Sort values
sort(vals.begin(), vals.end());
// Rearrange in wiggle pattern
vector<int> ans(vals.size());
int left = 0, right = 1;
for (int i = 0; i < vals.size(); i++) {
if (i % 2 == 0) {
ans[left] = vals[i];
left += 2;
} else {
ans[right] = vals[i];
right += 2;
}
}
// Update linked list
curr = head;
for (int val : ans) {
curr->val = val;
curr = curr->next;
}
return head;
}
};
Go
func wiggleSort(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
var vals []int
curr := head
// Collect all values
for curr != nil {
vals = append(vals, curr.Val)
curr = curr.Next
}
// Sort values
sort.Ints(vals)
// Rearrange in wiggle pattern
ans := make([]int, len(vals))
left, right := 0, 1
for i, val := range vals {
if i%2 == 0 {
ans[left] = val
left += 2
} else {
ans[right] = val
right += 2
}
}
// Update linked list
curr = head
for _, val := range ans {
curr.Val = val
curr = curr.Next
}
return head
}
Java
class Solution {
public ListNode wiggleSort(ListNode head) {
if (head == null || head.next == null) return head;
List<Integer> vals = new ArrayList<>();
ListNode curr = head;
// Collect all values
while (curr != null) {
vals.add(curr.val);
curr = curr.next;
}
// Sort values
Collections.sort(vals);
// Rearrange in wiggle pattern
int[] ans = new int[vals.size()];
int left = 0, right = 1;
for (int i = 0; i < vals.size(); i++) {
if (i % 2 == 0) {
ans[left] = vals.get(i);
left += 2;
} else {
ans[right] = vals.get(i);
right += 2;
}
}
// Update linked list
curr = head;
for (int val : ans) {
curr.val = val;
curr = curr.next;
}
return head;
}
}
Kotlin
class Solution {
fun wiggleSort(head: ListNode?): ListNode? {
if (head?.next == null) return head
val vals = mutableListOf<Int>()
var curr = head
// Collect all values
while (curr != null) {
vals.add(curr.`val`)
curr = curr.next
}
// Sort values
vals.sort()
// Rearrange in wiggle pattern
val ans = IntArray(vals.size)
var left = 0
var right = 1
for (i in vals.indices) {
if (i % 2 == 0) {
ans[left] = vals[i]
left += 2
} else {
ans[right] = vals[i]
right += 2
}
}
// Update linked list
curr = head
for (value in ans) {
curr!!.`val` = value
curr = curr.next
}
return head
}
}
Python
class Solution:
def wiggleSort(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
vals = []
curr = head
# Collect all values
while curr:
vals.append(curr.val)
curr = curr.next
# Sort values
vals.sort()
# Rearrange in wiggle pattern
ans = [0] * len(vals)
left, right = 0, 1
for i, val in enumerate(vals):
if i % 2 == 0:
ans[left] = val
left += 2
else:
ans[right] = val
right += 2
# Update linked list
curr = head
for val in ans:
curr.val = val
curr = curr.next
return head
Rust
impl Solution {
pub fn wiggle_sort(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
if head.is_none() || head.as_ref().unwrap().next.is_none() {
return head;
}
let mut vals = Vec::new();
let mut curr = &head;
// Collect all values
while let Some(node) = curr {
vals.push(node.val);
curr = &node.next;
}
// Sort values
vals.sort();
// Rearrange in wiggle pattern
let mut ans = vec![0; vals.len()];
let mut left = 0;
let mut right = 1;
for (i, &val) in vals.iter().enumerate() {
if i % 2 == 0 {
ans[left] = val;
left += 2;
} else {
ans[right] = val;
right += 2;
}
}
// Update linked list
let mut head = head;
let mut curr = head.as_mut();
for &val in &ans {
if let Some(node) = curr {
node.val = val;
curr = node.next.as_mut();
}
}
head
}
}
TypeScript
class Solution {
wiggleSort(head: ListNode | null): ListNode | null {
if (!head || !head.next) return head;
const vals: number[] = [];
let curr: ListNode | null = head;
// Collect all values
while (curr) {
vals.push(curr.val);
curr = curr.next;
}
// Sort values
vals.sort((a, b) => a - b);
// Rearrange in wiggle pattern
const ans: number[] = new Array(vals.length);
let left = 0, right = 1;
for (let i = 0; i < vals.length; i++) {
if (i % 2 === 0) {
ans[left] = vals[i];
left += 2;
} else {
ans[right] = vals[i];
right += 2;
}
}
// Update linked list
curr = head;
for (const val of ans) {
curr!.val = val;
curr = curr!.next;
}
return head;
}
}
Complexity
- ⏰ Time complexity:
O(n log n), where n is the number of nodes. The sorting step dominates the time complexity - 🧺 Space complexity:
O(n), for storing the values in arrays during the rearrangement process