Reorder List
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]
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; }}