Rearrange a Linked List in Zig-Zag fashion Medium 0 attempts
GeeksforGeeks ↗

Rearrange a Linked List in Zig-Zag fashion

Medium Linked List GeeksforGeeks

Reorder a linked list so its values alternate between dips and peaks — each element should be either no greater than both neighbors or no smaller than both, giving a pattern like a <= b >= c <= d >= e .... Equal values are allowed, and swapping node values is permitted

Input Format
Implement zigZagList(head). Inputs below show JavaScript function arguments; there is no stdin parsing. Linked lists use value arrays. The editor passes nodes with val and next properties; [] becomes null.
Output Format
Modify argument 1 in place. The editor compares its final value; the function return value is ignored. Returned list heads are displayed as value arrays; a null head is []. Any result satisfying the statement is accepted.

Sample Input and Output

Example 1 · Run Sample

Input
head = [4,3,7,8,6,2,1]
Output
[3,7,4,8,2,6,1]

Example 2

Input
head = [1]
Output
[1]
Constraints
  • 1 <= N <= 10^4
Test Cases (2)
Case 1
Args: [[4,3,7,8,6,2,1]] Expected: [3,7,4,8,2,6,1]
Case 2
Args: [[1]] Expected: [1]
Topics
Linked List

Swap Values

javascript
function zigZagList(head) {
  let curr = head, flag = true;
  while (curr && curr.next) {
    if ((flag && curr.val > curr.next.val) || (!flag && curr.val < curr.next.val))
      [curr.val, curr.next.val] = [curr.next.val, curr.val];
    curr = curr.next; flag = !flag;
  }
}

Time: O(n) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript