Wiggle Sort Linked List

Problem

Given a linked list, rearrange the node values such that they appear in alternating low -> high -> low -> high … form.

Examples

Example 1

1
2
3


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

1
2
3


Input: 5 -> 4 -> 3 -> 2 -> 1
Output: 4 -> 5 -> 2 -> 3 -> 1
Explanation: After rearranging: 4 < 5 > 2 < 3 > 1

Example 3

1
2
3


Input: 1
Output: 1
Explanation: Single node remains unchanged

Example 4

1
2
3


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


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

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Solution#

Method 1 - In-Place Value Swapping#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Sort and Rearrange#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Example 3

Example 4

Solution

Method 1 - In-Place Value Swapping

Intuition

Approach

Code

Complexity

Method 2 - Sort and Rearrange

Intuition

Approach

Code

Complexity