Reorder List
Reorder a linked list from L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1 -> ... in place.
- The number of nodes in the list is in the range [1, 5 * 10⁴].
- 1 <= Node.val <= 1000
Intuition
Reorder list rearranges a list from L0 → L1 → … → Ln into L0 → Ln → L1 → Ln-1 → …, interleaving from both ends. It must be done in place, without altering node values.
The difficulty is that a singly linked list cannot be walked backwards, yet the target order needs nodes from the tail. Copying node references into an array solves it at O(n) space; the in-place solution composes three standard techniques:
- Find the middle, reverse the second half, then merge the two halves alternately.
Each piece is a problem you already know — Middle of the Linked List, Reverse Linked List, and a merge — which is what makes this worth recognising rather than inventing.
After reversing the second half, the two halves run in opposite directions, so taking one node from each in turn produces exactly the required interleaving.
The step that breaks implementations is severing the first half. After locating the middle, the first half's tail must be set to null. Without it the halves remain connected, the reversal creates a cycle, and the merge loops forever.
For odd-length lists the first half should hold the extra node, so the interleaving ends cleanly on the middle element. The two-speed walk with fast && fast.next as the condition gives this naturally.
The merge must handle the halves differing in length by one, stopping when the second half is exhausted.
Three linear passes give O(n) time and O(1) space, against O(n) space for the array approach.
Three textbook sub-routines composed: find the middle with slow/fast, reverse the second half, then zip the two halves together. Recognising a problem as a composition of known primitives — rather than one new algorithm — is what makes it tractable in an interview.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(1) space.
See why the tail is hard to reach
The target order needs nodes from the end, but a singly linked list cannot be walked backwards. Reversing half the list is what makes them reachable.
Find the middle
Advance one pointer two nodes for every one the other moves. With fast && fast.next as the condition, the first half keeps the extra node on odd-length lists.
Sever the first half
Set the first half's tail to null. Leaving the halves connected turns the reversal into a cycle and the merge never terminates — the defining bug here.
Reverse the second half
Rewrite the next pointers in place. The halves now run in opposite directions, which is what the alternating merge requires.
Merge alternately
Take one node from each half in turn. The halves can differ in length by one, so stop when the second is exhausted.
Recognise the composition
This is Middle of the Linked List, Reverse Linked List, and a merge in sequence. Naming the pieces makes it routine rather than something to invent.
Cost of the approach
Three linear passes give O(n) time and O(1) space, against O(n) space for the array-of-references alternative.
Solution & live demo
Common pitfalls
Not severing the first half
second = slow.next # reverse second...
second = slow.next slow.next = None
Without cutting, the first half's tail still points into the second half, which after reversal points back — creating a cycle. The merge loop then never terminates.
Starting fast at head instead of head.next
slow, fast = head, head
slow, fast = head, head.next
On an even-length list this leaves slow one node too far right, so the second half is shorter than the first and the interleave drops a node. Starting fast one ahead makes slow stop at the end of the first half for both parities.
Not saving both next pointers before relinking
first.next = second second.next = first.next
f, s = first.next, second.next first.next = second second.next = f
The first assignment overwrites first.next, so reading it afterwards yields the node just linked rather than the original successor — the list folds back on itself. Both successors must be captured before any pointer is written.
Edge cases
Already in the target order — return early.
The pattern is unchanged, so the merge is a no-op.
The reversed half still links back into the first, producing a cycle.
The middle node ends up last, which the slow/fast convention handles without a special case.