Q34: Reorder Linked List
Reorder a singly linked list $L_0 \to L_1 \to \dots \to L_{n-1} \to L_n$ into $L_0 \to L_n \to L_1 \to L_{n-1} \to L_2 \to L_{n-2} \dots$ in-place.
In-Place Linked List Interleaving
function reorderList(head) {
if (!head || !head.next) return;
// 1. Find middle node
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// 2. Reverse second half
let prev = null, curr = slow.next;
slow.next = null;
while (curr) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
// 3. Interleave first half and reversed second half
let first = head, second = prev;
while (second) {
let tmp1 = first.next;
let tmp2 = second.next;
first.next = second;
second.next = tmp1;
first = tmp1;
second = tmp2;
}
}💡 Finds middle using slow/fast pointers, splits list, reverses second half, and weaves node pointers alternating between first and second sublists.
Key Takeaways
- 1) Find middle using Fast/Slow pointers. 2) Reverse second half. 3) Interleave nodes from both halves.
- Performs transformation in $O(n)$ time and $O(1)$ space.
Knowledge Check
What three sub-algorithms are combined to solve the Reorder List problem in-place?