Reorder List

Medium

Problem

Reorder L0 → L1 → … → Ln−1 → Ln into L0 → Ln → L1 → Ln−1 → L2 → … in place, by relinking the nodes (do not just change their values).

Example 1

Input:  1 → 2 → 3 → 4 → 5
Output: 1 → 5 → 2 → 4 → 3

Test cases

Case 1

Input:    [1,2,3,4]
Expected: [1,4,2,3]

Case 2

Input:    [1,2,3,4,5]
Expected: [1,5,2,4,3]

Case 3

Input:    [1,2]
Expected: [1,2]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Middle + reverse + merge

Time O(n)Space O(1)

L0→Ln→L1→Ln−1…: split at the middle (fast/slow), reverse the second half, then weave the two halves together.

function reorderList(head) {
let slow = head, fast = head;
while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; }
let prev = null, cur = slow.next;
slow.next = null;
while (cur) { const nx = cur.next; cur.next = prev; prev = cur; cur = nx; }
let a = head, b = prev;
while (b) {
const an = a.next, bn = b.next;
a.next = b; b.next = an;
a = an; b = bn;
}
}