Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Reorder L0→L1→…→Ln into L0→Ln→L1→Ln-1→… in three in-place phases: (1) find the middle with slow/fast pointers, (2) reverse the second half, (3) merge the two halves by alternating nodes. Each phase is a linear pass, so the whole thing is O(n) time and O(1) space — no array, no node allocation.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can decompose a compound list transformation into the three known subroutines and execute each in place without losing pointers — the integration test of linked-list fundamentals.
Where candidates slip
Forgetting to sever the first half (slow.next = null), creating a cycle; or mishandling the merge's saved-next pointers; or using the wrong middle so halves are mismatched.
How to stand out
Name the three phases up front, justify which half keeps the extra node for odd/even lengths, do it in O(1) space, and mention the O(n)-space array version as the simpler-but-heavier alternative.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewReorder L0→Ln→L1→…Is O(1) extra space required?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Array of Nodes — Two-Pointer by Index
1Hint 1Explore hintHide hint
If you could randomly index the nodes like an array, reordering L0, Ln, L1, Ln-1 would just be reading from both ends inward. Linked lists lack random access — how do you fake it?
2Hint 2Explore hintHide hint
Walk the list once, pushing every node reference into an array. Now you have O(1) indexed access.
3Hint 3Explore hintHide hint
Use left=0 and right=n-1. Alternately attach nodes[left] then nodes[right], advancing inward, and remember to terminate the final node's next at null.
A · Core idea
We buy random access by copying node references into an array, then relink them in the reordered sequence using two indices converging from the ends.
Why an array helps. The target order L0, Ln, L1, Ln-1, … is trivially expressed as 'front, back, front+1, back-1, …' — but a singly linked list can't jump to the back. Dumping the n node references into an array gives O(1) access to any position, so the reorder becomes a simple two-pointer walk.
The relink loop. With left starting at 0 and right at n−1, we alternate: link nodes[left] to nodes[right], then nodes[right] to nodes[left+1], advancing left++ and right--. We stop when the pointers meet, and finally set the last node's next to null so the list terminates instead of looping.
Why we don't ship this as the headline. It's correct and easy to explain, and the relinking is far less error-prone than in-place pointer surgery. But it spends O(n) memory storing references — which the cleaner three-phase method avoids entirely. State it as the baseline, then show you can do better.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
head = [1, 2, 3, 4]left=0,right=3
n1.next=n4; n4.next=n2
1→4→2 …[1, 4, 2, 3]C · Code with teaching comments
Reference implementation previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Storing node references (not values) is the key: we still relink the original nodes, satisfying the 'don't modify values' rule, while gaining array-style indexing. It's the honest, low-risk answer that sets up the O(1) optimization.
ComplexityO(n) time, O(n) space — One pass to fill the array (O(n)) plus one pass with two indices to relink (O(n)). The array of n node references is O(n) extra space.
E · Edge cases and pitfalls3Storing values instead of node references — then you'd be copying values, which the prompt forbids.Explore edge casesHide edge cases
Pitfalls
- Storing values instead of node references — then you'd be copying values, which the prompt forbids.
- Forgetting to null-terminate the last node, leaving a cycle.
- Off-by-one when left and right meet on odd-length lists.
Approach 2 of 2 · Optimal
In Place — Middle + Reverse + Merge (Optimal)
1Hint 1Explore hintHide hint
The target weaves the back of the list into the front. What if you literally split the list in half and reversed the back half so its order matched the weave?
2Hint 2Explore hintHide hint
Phase 1: find the middle with slow/fast pointers. Phase 2: reverse the second half (the classic prev/curr/next flip). Phase 3: merge the two halves by alternating one node from each.
3Hint 3Explore hintHide hint
Cut the first half by setting slow.next = null before reversing. In the merge, save both lists' next pointers before relinking, and stop when the reversed second half is exhausted.
A · Core idea
We realise the interleaving by physically splitting, flipping, and zipping the list.
Phase 1 — find the middle (slow/fast). Advance slow by one and fast by two. Using the guard fast.next && fast.next.next, when fast stops, slow sits at the end of the first half. For even lengths this gives the first half the extra node, which is exactly what makes the later merge terminate cleanly.
Phase 2 — reverse the second half. Record second = slow.next, then sever the first half with slow.next = null so it terminates. Reverse the second chain with the standard three-pointer flip; prev ends as the head of the reversed back half. After this we have two independent lists: head (first half, in order) and prev (second half, reversed).
Phase 3 — merge by alternating. Walk both lists together. Each step, stash t1 = first.next and t2 = second.next, then weave: first.next = second; second.next = t1. Advance first = t1 and second = t2. The reversed second half is the same length or one shorter than the first half, so the loop naturally ends when second becomes null, leaving the first half's final node correctly terminating the list.
Why the lengths line up. Because Phase 1 gives the first half the extra node on even lengths (and the exact middle on odd lengths), the second (reversed) half never overruns the first. That's the invariant that lets us drive the merge by 'while second != null' without a dangling pointer.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
head = [1, 2, 3, 4, 5]Array state
start
slow=1, fast=1
[1, 5, 2, 4, 3]C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The problem is not one clever algorithm — it's three boring ones composed correctly. The art is the bookkeeping: sever the halves so you don't build a cycle, and save both next-pointers in the merge so you don't strand a chain. Master each primitive alone and Reorder List is free.
ComplexityO(n) time, O(1) space — Three sequential linear passes — find middle, reverse, merge — sum to O(n). Each phase uses only a constant number of pointers, so O(1) extra space.
E · Edge cases and pitfalls6head = [1] — Guard returns immediately (head.next == null); a single node is already reordered.Explore edge casesHide edge cases
Edge cases handled
head = [1]Guard returns immediately (head.next == null); a single node is already reordered.head = [1, 2]slow stays at node 1, second half is [2] reversed to [2], merge links 1→2 → unchanged.head = [1, 2, 3, 4]slow stops at node 2, second half [3,4]→[4,3], merge → 1→4→2→3.
Pitfalls
- Forgetting slow.next = null — the two halves stay connected and the merge creates a cycle.
- Not saving both next-pointers in the merge — you strand one of the chains.
- Using the wrong middle guard so the second half is longer than the first, overrunning the merge.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic void reorderList(ListNode head) { if (head == null || head.next == null) return; // Phase 1: find the middle (slow ends at end of first half) ListNode slow = head, fast = head;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Building a cycle by not cutting the list
If slow.next still points into the second half when you merge, the reordered list loops back on itself forever.
Explore the code comparisonHide the code comparison
Building a cycle by not cutting the list
If slow.next still points into the second half when you merge, the reordered list loops back on itself forever.
Don't write this
second = slow.next
# forgot: slow.next = None
prev = None
while second:
nxt = second.next
second.next = prev
prev = second
second = nxtWrite this instead
second = slow.next
slow.next = None # sever the halves first
prev = None
while second:
nxt = second.next
second.next = prev
prev = second
second = nxt2Stranding a chain in the merge
Relinking first.next = second before saving the old first.next loses the rest of the first half.
Explore the code comparisonHide the code comparison
Stranding a chain in the merge
Relinking first.next = second before saving the old first.next loses the rest of the first half.
Don't write this
while (second != null) {
first.next = second; // lost old first.next
second.next = first.next; // now points to itself
first = first.next;
second = second.next;
}Write this instead
while (second != null) {
ListNode t1 = first.next, t2 = second.next;
first.next = second;
second.next = t1;
first = t1;
second = t2;
}Revise
Carry the pattern into the interview
Pattern to remember
Find middle (slow/fast) → reverse second half → interleave merge
Code pattern to memorize
# 1. middle
slow=fast=head
while fast.next and fast.next.next: slow=slow.next; fast=fast.next.next
# 2. reverse second half from slow.next
second=slow.next; slow.next=None; prev=None
while second: nxt=second.next; second.next=prev; prev=second; second=nxt
# 3. merge first half (head) with reversed second (prev)
first=head; second=prev
while second: t1=first.next; t2=second.next; first.next=second; second.next=t1; first=t1; second=t2Rules to remember
- 1Cut the list: after finding the middle, set
slow.next = Noneso the first half terminates cleanly. - 2The first half is the same length or one longer than the second — that's why the merge loop ends when the reversed second half runs out.
- 3Save both
nextpointers (first.nextandsecond.next) before relinking in the merge, or you lose track of the rest. - 4Use the
fast.next && fast.next.nextmiddle so for even lengthsslowlands on the end of the first half (the first half gets the extra node). - 5It's three textbook subroutines glued together — middle-finding, reversal, merge — don't try to do it in one clever pass.
Use this pattern when
- Rearrange a singly linked list by interleaving its front and back
- Any problem decomposable into find-middle + reverse + merge on a list
- Palindrome checks and fold/zip operations on linked lists
- When O(1) space is required and you can't dump nodes into an array
Choose another pattern when
- O(n) extra space is acceptable and clarity matters more → dump nodes into an array and two-pointer by index
- It's a doubly linked list → you can walk backwards directly, no reversal needed
- You only need to read, not rewrite, the order → just traverse with two indices
Interview takeaway
Reorder List is the canonical 'compose three linked-list primitives' problem. If you've drilled find-middle, reverse, and merge separately, this is just gluing them — which is exactly what the interviewer is checking.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternComposition of three linked-list primitives — find-middle (slow/fast), in-place reversal, and two-pointer merge. The same trio underlies Palindrome Linked List and the merge phase of Sort List; recognising the decomposition is the whole skill.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Reverse Linked ListPhase 2 of this problem in isolation — the prev/curr/next flip.
- Palindrome Linked ListFind middle + reverse second half, then compare instead of merge.
- Middle of the Linked ListPhase 1 alone — slow/fast pointers to locate the midpoint.
- Reverse Nodes in k-GroupGeneralises the split-and-reverse idea to fixed-size groups.