Rearrange a given linked list in-place Medium 0 attempts
GeeksforGeeks ↗

Rearrange a given linked list in-place

Medium Linked List GeeksforGeeks

You're given a singly linked list L0 → L1 → ... → Ln. Reorder it in place by alternating from the two ends inward: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 ...

Input Format
Implement rearrange(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 [].

Sample Input and Output

Example 1 · Run Sample

Input
head = [1,2,3,4,5]
Output
[1,5,2,4,3]

Example 2

Input
head = [1]
Output
[1]
Constraints
  • 1 to 5 * 10^4 nodes
  • 1 <= Node.val <= 1000
Test Cases (2)
Case 1
Args: [[1,2,3,4,5]] Expected: [1,5,2,4,3]
Case 2
Args: [[1]] Expected: [1]
Topics
Linked List

Find Mid + Reverse + Interleave

javascript
function rearrange(head) {
  let slow = head, fast = head;
  while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; }
  let second = slow.next; slow.next = null;
  let prev = null;
  while (second) { const next = second.next; second.next = prev; prev = second; second = next; }
  let first = head; second = prev;
  while (second) { const n1 = first.next, n2 = second.next; first.next = second; second.next = n1; first = n1; second = n2; }
}

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

Saved in this browser only. Private to you.

JavaScript