ASAPUtils
The composition
This medium problem is three familiar operations, not one new trick:
- find the end of the first half with slow/fast;
- reverse the second half;
- weave one node from each half.
Optimal solution
void reorderList(ListNode* head) {
if (!head || !head->next) return;
ListNode *slow = head, *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *prev = nullptr, *curr = slow->next;
slow->next = nullptr;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
ListNode *first = head, *second = prev;
while (second) {
ListNode *a = first->next, *b = second->next;
first->next = second;
second->next = a;
first = a;
second = b;
}
}
function reorderList(head) {
if (!head?.next) return;
let slow = head, fast = head;
while (fast.next?.next) {
slow = slow.next;
fast = fast.next.next;
}
let prev = null, curr = slow.next;
slow.next = null;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
let first = head, second = prev;
while (second) {
const a = first.next, b = second.next;
first.next = second;
second.next = a;
first = a;
second = b;
}
}
Correctness
The first phase splits the original order into a forward first half and forward second half. Reversal makes the second half appear in Ln,Ln-1,… order. Each weave iteration appends the next required node from the first half and then the next required node from that reversed half.
Complexity
Each phase is linear and phases are sequential, so O(n) time. Only pointer variables are used: O(1) space.
Traps
- Using a middle condition that splits even-length lists incorrectly.
- Forgetting
slow.next = nulland accidentally creating a cycle. - Changing a next link before saving both halves’ successors.
- Continuing until
firstis null rather than until the shorter second half is exhausted.
Blank re-solve prompt
Say “middle, reverse, weave” before coding. Trace both four and five nodes because even and odd splits expose different off-by-one mistakes.