Rearrange a given linked list in-place | Problems

Given a singly linked list L0→L1→...→Ln, rearrange it to L0→Ln→L1→Ln-1→L2→Ln-2...

Example: 1→2→3→4→5 → 1→5→2→4→3

Sample Input

—

Sample Output

—

Constraints

1 to 5 * 10^4 nodes
1 <= Node.val <= 1000

Topics

Linked List

Find Mid + Reverse + Interleave

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.