Approach Summary
Three steps: find middle with slow/fast pointers, reverse the second half, merge two halves alternately.
Full Solution & Approach
Reordering L0 → Ln → L1 → Ln-1 → … is an interleaving of the first half with the reversed second half. Split it into three phases. Find the middle node with slow and fast pointers (fast moves twice as fast), which also splits the list in half. Reverse the second half in place using the standard three-pointer reversal. Finally merge the two halves alternately: take one node from the first half, then one from the reversed second half, threading pointers until both are exhausted. A subtle detail: the first half may be one node longer than the second on odd lengths, so the merge must stop when the second half runs out, leaving the last node of the first half pointing to null. Each phase is a single linear pass, so the total is O(n) time with O(1) extra space.
Finding the middle, reversing, and merging are each O(n) — O(n) total time. All operations rewire pointers in place — O(1) extra space.
Solution Code
Solution
def reorder_list(head) -> None:
if not head or not head.next:
return
# 1) find middle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 2) reverse second half
prev, cur = None, slow
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
# 3) interleave
first, second = head, prev
while second.next:
first.next, first = second, first.next
second.next, second = first, second.nextfunction reorderList(head) {
if (!head || !head.next) return;
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
let prev = null, cur = slow;
while (cur) {
const next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
let first = head, second = prev;
while (second.next) {
const fNext = first.next, sNext = second.next;
first.next = second;
second.next = fNext;
first = fNext;
second = sNext;
}
}public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
// 1) find middle
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 2) reverse second half
ListNode prev = null, cur = slow;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
// 3) interleave
ListNode first = head, second = prev;
while (second.next != null) {
ListNode tmp1 = first.next;
ListNode tmp2 = second.next;
first.next = second;
second.next = tmp1;
first = tmp1;
second = tmp2;
}
}void reorderList(ListNode* head) {
if (!head || !head->next) return;
// 1) find middle
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// 2) reverse second half
ListNode* prev = nullptr;
ListNode* cur = slow;
while (cur) {
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
// 3) interleave
ListNode* first = head;
ListNode* second = prev;
while (second->next) {
ListNode* tmp1 = first->next;
ListNode* tmp2 = second->next;
first->next = second;
second->next = tmp1;
first = tmp1;
second = tmp2;
}
}Edge Cases to Watch
- Empty or single-node list — nothing to reorder
- Odd-length list — the first half has the extra node
- Two-node list — order is unchanged in effect
- All nodes equal — the interleaving is still structurally correct
How to Recognize This Pattern
- Interleave first half with reversed second half
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)