Learn › DSA Patterns › In-Place Linked List Reversal › Case Study
Reorder List:
6 Bugs to a Clean Solution
Not a tutorial — a real debugging log. Seven attempts, six distinct bugs, each one reproduced with a concrete failing input before it was fixed.
The Problem
LeetCode 143 — Reorder List
Given the head of a singly linked
list L0 → L1 → … → Ln, reorder it
in place to
L0 → Ln → L1 → Ln-1 → ….
You may not modify the node values — only the
next pointers. The function
returns nothing.
Input
1→2→3→4→5 Output
1→5→2→4→3 Input
1→2→3→4 Output
1→4→2→3 Input
[1] (single node) Output
[1] The one obstacle the whole problem reduces to
The output alternates front, back, front, back. Walking forward is easy.
Walking backward is impossible in a singly linked list — there is no
prev field. Everything else in this solution
exists to work around that single constraint.
The Decomposition
Three Problems, Not One
You cannot walk backward — but you can build a list that already points backward. That turns one hard problem into three familiar ones.
Find the middle & cut
Slow/fast pointers locate the boundary in one pass. Save the second half, then sever with slow.next = null.
LeetCode 876Reverse the second half
The prev / curr / temp three-pointer flip. Now both halves can be walked forward — one from the front, one from the back.
LeetCode 206Weave them together
Take one node from each list, alternating. Rescue both next pointers before rewiring anything.
LeetCode 21 (variant)The Journey
Attempt by Attempt
Every bug below was reproduced with a real failing input before being fixed — not just described.
function reorderList(head: ListNode | null): void {
let next;
let temp;
while (head) {
if (!head.next) temp = head; // head never advances
}
while (head) {
}
}The function hangs on any non-empty input. Nothing is reordered, and it never returns.
The loop body reads head.next but never assigns to head, so the condition while (head) is true forever. Underneath the hang sits a bigger problem: the sketch is reaching for "find the last node," and repeating that for every position is O(N²). The reorder pattern needs the back of the list walked forward, not re-scanned.
Proof — trace on 1→2→3→4→5:
iter1: head=N0(1). head.next=N1(2) is truthy → if body skipped. head unchanged. iter2: head=N0(1) (unchanged). Same check, same result. head unchanged. ...repeats forever — while (head) never becomes false. Expected: 1→5→2→4→3. Got: infinite loop, the function never returns. Separately: even with an advance line, scanning for the last node once per output position costs O(N²) on a 10⁴-node input.
Every while loop over a linked list must end with a line that advances the pointer. Then replace the "find the last node" plan with a decomposition: find the middle, reverse the second half, weave the two halves.
let slow = head, fast = head;
while (fast.next) { // throws once fast becomes null
slow = slow.next;
fast = fast.next.next;
}
let prev = null;
while (slow) {
const temp = slow.next;
slow.next = temp; // no-op, and slow never advances
}The slow/fast structure is correct now, but even-length inputs throw a TypeError, and odd-length inputs hang in the reverse loop.
Two independent defects. First, while (fast.next) omits the fast null check, and on even-length lists fast itself becomes null before the condition is re-tested. Second, slow.next = temp assigns slow.next back to itself — temp IS slow.next — so nothing flips and slow never advances.
Proof — two traces:
Even length, 1→2→3→4: iter1: fast=N0(1), fast.next=N1(2) truthy → slow=N1(2), fast=N2(3). iter2: fast=N2(3), fast.next=N3(4) truthy → slow=N2(3), fast = 3.next.next = null. check: reading fast.next where fast is null → CRASH: Cannot read properties of null (reading 'next') Odd length, 1→2→3→4→5 (survives phase 1, slow=N2(3)): iter1: temp = slow.next. slow.next = temp → assigns the same value back. Nothing changed. slow unchanged. iter2: identical. ...repeats forever. Expected: 1→4→2→3 and 1→5→2→4→3. Got: TypeError on even lengths, infinite loop on odd lengths.
Guard both pointers with while (fast && fast.next). In the reverse loop, flip toward prev — not back onto itself — and advance every iteration.
while (fast && fast.next) { // fixed
slow = slow.next;
fast = fast.next.next;
}
let prev = null, second = slow.next;
while (second) {
const temp = second.next;
second.next = prev;
prev = temp; // should be prev = second
second = second.next; // reads the pointer just overwritten
}Phase 1 is finally correct. The reverse loop now exits — but after a single iteration, leaving one node flipped and one node orphaned.
The two advance lines are crossed. prev should become the node just flipped (second), not the rescued temp. And second = second.next reads a pointer that line two overwrote one statement earlier — so it follows the freshly reversed link backward instead of continuing forward. temp was rescued for exactly this purpose and then ignored.
Proof — trace the reverse on second = 4→5:
Initial: prev=null, second=N3(4).
iter1: temp = 4.next = N4(5).
4.next = prev = null → list now reads 4→null
prev = temp = N4(5) ← wrong: should be N3(4)
second = second.next = 4.next = null ← 4.next was just overwritten with null
loop exits after ONE iteration.
Expected: 5→4→null, with prev pointing at node 5 as the reversed head.
Got: node 5 never flipped (5.next still null by luck), node 4 orphaned with nothing pointing to it, and prev holding node 5 for the wrong reason. prev = second (the node you just finished), and second = temp (the rescue you already made). Never read a .next you overwrote on the line above.
let prev = null, second = slow.next;
// missing: slow.next = null
while (second) {
const temp = second.next;
second.next = prev;
prev = second; // fixed
second = temp; // fixed
}
// missing: phase 3 — nothing is ever wovenNo crash, no hang, and the reversal itself is textbook-correct. The function simply does not reorder anything — it returns having done half the work.
This is the quiet failure mode that no error message points at. The second half is reversed correctly, but slow.next = null was never written, so the two halves still share a node. And phase 3 does not exist at all, so the two lists are never woven together. The function mutates the list into something that is neither the input nor the answer.
Proof — trace on 1→2→3→4→5:
phase 1: slow=N2(3). second = slow.next = N3(4). No cut — 3.next still points at N3(4). phase 2: prev = 5→4→null (correct reversal of the second half). phase 3: absent. Resulting head chain: 1→2→3→4→null ← node 4 belongs to BOTH lists, and node 5 is unreachable from head. Expected: 1→5→2→4→3. Got: 1→2→3→4 — node 5 dropped entirely, nothing woven.
Add slow.next = null immediately after saving second — that gives the first half a terminator and stops the halves sharing a node. Then write the weave loop.
if (!head) return null; // void function cannot return a value
// ... phase 1 ...
let prev = null, second = slow.next;
// still no cut
while (second) { /* reverse — correct */ }
while (head && second) { // second is null here — body never runs
/* weave */
}The weave loop is written and correct in isolation, but its body never executes even once. Output is still missing nodes.
The reverse loop is while (second) — it can only exit once second is null, by construction. Driving the weave from second therefore guards on a value that is guaranteed null at that point, so the loop is skipped silently. prev is the variable that spent the entire reverse loop accumulating the answer. Separately, return null in a void function is a TypeScript type error.
Proof — trace on 1→2→3→4→5:
phase 2 exits precisely BECAUSE second became null — that is the exit condition. phase 3: while (head && second) → second is null → condition false → body never runs. Still no cut, so the head chain reads 1→2→3→4→null. Expected: 1→5→2→4→3. Got: 1→2→3→4 — identical to the previous attempt, because the weave contributed nothing. Also: `return null` in a function typed `: void` fails to compile under strictNullChecks.
Drive the weave from prev, not second. Ask on every loop: which variable is my answer, and which was only ever steering the loop?
let prev = null, second = slow.next; slow.next = null,
while (second) { // error TS1109: Expression expected
const temp = second.next;
second.next = prev;
prev = second;
second = temp;
}Every phase is now algorithmically correct, but the file does not compile: error TS1109: Expression expected.
Two statements were merged into one declaration list. slow.next is a property access, not a binding name, so it cannot appear in a let declaration — and the line terminates with a comma instead of a semicolon. The comma operator expects another expression to follow, finds the while keyword (a statement, not an expression), and the parser reports the error at the while, one line below the real mistake.
Proof — what the parser sees:
Source:
let prev = null, second = slow.next; slow.next = null,
while (second) {
Parse: `slow.next = null` is a valid expression. The trailing `,` opens a comma-operator sequence and demands a second expression.
Next token: `while` — a statement keyword, never a valid expression operand.
→ error TS1109: Expression expected, reported at line 27, char 5 (the `while`).
Lesson: the reported line is where the parser gave up, not where the mistake is. Look one line above. Split it into two statements: `let prev = null, second = slow.next;` then `slow.next = null;` on its own line.
// O(N) time, O(1) space — find middle, reverse, weave
function reorderList(head: ListNode | null): void {
if (!head) return;
// Phase 1 — slow lands on the middle node
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// Save the second half, THEN cut
let prev: ListNode | null = null;
let second = slow.next;
slow.next = null;
// Phase 2 — reverse the second half
while (second) {
const temp = second.next; // 1. rescue
second.next = prev; // 2. flip
prev = second; // 3. advance prev
second = temp; // 4. advance second
}
// Phase 3 — weave the two halves together
let first = head;
while (first && prev) {
const f = first.next; // rescue both...
const s = prev.next; // ...before touching anything
first.next = prev; // 1 → 5
prev.next = f; // 5 → 2
first = f;
prev = s;
}
}
// 1→2→3→4→5 becomes 1→5→2→4→3All six issues are resolved: both loops advance, fast is null-guarded, the reverse flips toward prev and advances via the rescued temp, the halves are cut apart, the weave is driven by prev, and the declaration is split into valid statements. Three linear passes, no nesting, and every pointer is a fixed local.
Proof — full trace on 1→2→3→4→5:
phase 1: slow: 1→2→3, fast: 1→3→5 → loop exits, slow=N2(3).
cut: second=N3(4), 3.next=null → first half 1→2→3, second half 4→5.
phase 2: iter1 temp=5, 4.next=null, prev=4, second=5.
iter2 temp=null, 5.next=4, prev=5, second=null → exit. Reversed: 5→4.
phase 3: iter1 f=2, s=4. 1.next=5, 5.next=2. first=2, prev=4.
iter2 f=3, s=null. 2.next=4, 4.next=3. first=3, prev=null → exit.
Result: 1→5→2→4→3 ✅
Also verified: 1→2→3→4 → 1→4→2→3; [1] returns unchanged; [1,2] returns unchanged; [] returns immediately via the guard. Interactive
Reorder Visualizer
All three phases on 1→2→3→4→5, one step at a time.
Start: 1→2→3→4→5. Target: 1→5→2→4→3.
Lessons Learned
Key Takeaways
Hard problems are usually three easy ones stacked
Reorder List is not one algorithm. It is find-the-middle (LC 876), reverse-a-list (LC 206), and merge-two-lists — glued together. Spotting that decomposition is the actual skill; each piece is something you have already solved.
Every while loop over a linked list needs an advance line
Three separate hangs in this journey came from the same omission. Write the advance line first, before the body, then fill in the middle — the loop can no longer run forever by accident.
Rescue a pointer before you overwrite it — then actually use the rescue
Saving temp and then reading second.next anyway is worse than not saving it, because the code looks correct. Before any .next assignment, ask: was anything reachable only through this pointer?
Cut the halves apart, or they share a node
Without slow.next = null the boundary node lives in both lists at once. Nothing throws — the weave just produces a wrong answer, and in other shapes a cycle that hangs the next loop.
Know which variable is the answer and which was only steering
while (second) exits precisely because second became null. Reaching for it afterwards guards on a guaranteed-null value and silently skips the entire weave. prev held the answer the whole time.
Pick the convention that makes the next loop trivial
Cutting after slow keeps the second half shorter than or equal to the first. That single choice is why the weave loop needs zero null checks in its body — and why the alternative split crashes on odd lengths.
Design Decision
Why Cut After slow?
A tempting shortcut is second = slow — it
avoids the null dereference on an empty list without a guard.
It also breaks the algorithm on odd lengths.
first: 1 → 2 → 3 second: 5 → 4 (second ≤ first, always)
The second half is never longer than the first. So whenever the second-half pointer is non-null, the first-half pointer must be too — the weave loop needs no null checks in its body, and the leftover first-half tail is already terminated by the cut.
first: 1 → 2
second: 5 → 4 → 3 (second LONGER on odd lengths)
step 1: 1→5, 5→2 first=2, sh=4
step 2: 2→4, 4→null first=null, sh=3
step 3: sh is 3, loop continues
→ reads first.next → 💥
Even lengths survive; odd lengths crash. And you still cannot cut — severing
1→2 from node 3 needs a pointer to node 2, which
slow has already passed. Tracking a
prevSlow is more code than the one-line guard it
was trying to avoid.
Final Result
The Verified Solution
Three passes, one direction each — find the middle, reverse the back, weave the two.
// O(N) time, O(1) space — find middle, reverse, weave
function reorderList(head: ListNode | null): void {
if (!head) return;
// Phase 1 — slow lands on the middle node
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// Save the second half, THEN cut
let prev: ListNode | null = null;
let second = slow.next;
slow.next = null;
// Phase 2 — reverse the second half
while (second) {
const temp = second.next; // 1. rescue
second.next = prev; // 2. flip
prev = second; // 3. advance prev
second = temp; // 4. advance second
}
// Phase 3 — weave the two halves together
let first = head;
while (first && prev) {
const f = first.next; // rescue both...
const s = prev.next; // ...before touching anything
first.next = prev; // 1 → 5
prev.next = f; // 5 → 2
first = f;
prev = s;
}
}
// 1→2→3→4→5 becomes 1→5→2→4→3| Solution | Time | Space | Verified |
|---|---|---|---|
| Find Middle + Reverse + Weave (Attempt 7) Verified ✓ | O(N) | O(1) | Odd, even, single-node, two-node, and empty cases |
| Copy nodes into an array, then re-link by index | O(N) | O(N) | Correct, but allocates a full array of node references |
| Re-scan for the last node on every output position | O(N²) | O(1) | The instinct behind attempt 1 — times out on large inputs |
Reuse This
Template: Split, Reverse, Recombine
The generic shape behind this solution — reach for it whenever a list problem needs the back half walked forward.
function splitReverseRecombine(head):
if head is null: return
// 1 — find the boundary
slow = head, fast = head
while fast is not null and fast.next is not null:
slow = slow.next
fast = fast.next.next
// 2 — save the tail half, THEN sever
second = slow.next
slow.next = null // without this the halves share a node
// 3 — reverse the tail half (prev / curr / temp)
prev = null
while second is not null:
temp = second.next // rescue
second.next = prev // flip
prev = second // advance prev
second = temp // advance curr, using the rescue
// 4 — recombine; prev is the reversed head, NOT second
first = head
while first is not null and prev is not null:
f = first.next // rescue both...
s = prev.next // ...before rewiring anything
first.next = prev
prev.next = f
first = f
prev = sWhen to reach for this
Any list problem that needs to compare or interleave the front with the back — reordering, palindrome checks, folding. O(1) space beats copying into an array.
The trap this journey hit
Overwriting a next pointer and then reading it on the very next line. Three of the six bugs above were that exact mistake wearing different clothes.
Test Yourself
Quiz: Check Your Understanding
Your score
0 / 6
Keep Learning
Bugs are part of the process 🎉
Six real bugs, six real fixes — that's what getting to a correct O(1)-space reorder actually looks like.
Next, while the middle-and-reverse muscle is warm: LeetCode 234 — Palindrome Linked List (two-thirds of what you just wrote), then LeetCode 148 — Sort List and LeetCode 25 — Reverse Nodes in k-Group. The full reversal walkthrough lives in the Reverse Linked List case study.