Linked-list reversal

The problem it solves

Turn a singly linked list around, in place: the head becomes the tail, every arrow flips, and no extra memory is spent. As a standalone task it is modest; as an interview instrument it is the most-asked pointer question in existence, because it is the smallest problem that tests whether a candidate can mutate linked structure without losing hold of it. There is exactly one way to get it right, three canonical ways to get it wrong, and no way to fake it — the code is six lines and each one is load-bearing.

It also earns its keep as a building block. Reverse-in-k-groups is this loop plus stitching. Palindrome-list checks reverse the back half and compare inward. Reorder-list (first, last, second, second-last…) reverses the second half and merges. Each of those “hard” problems is this page’s loop wearing scaffolding, which is why interviewers check the loop first: a candidate who fumbles the primitive has no chance at the composites.

The intuition — and where it breaks down

Walk the list with three fingers. curr marks the node being processed. prev marks everything already flipped — a growing, fully reversed prefix hanging behind you. next is the finger you dare not lift: it holds your place in the unflipped remainder. At each node, one move: point curr’s arrow backwards at prev, then shuffle all three fingers one node forward. When curr walks off the end, prev is standing on the old tail — the new head.

The intuition’s crux is why the third finger is not optional. In a singly linked list, curr.next is the only reference to the rest of the list. The flip overwrites it. Save it first and the walk continues; overwrite it first and the entire unprocessed tail becomes unreachable — not corrupted, gone, orphaned with no pointer in the program able to reach it. The player letters NEXT above the node being protected at each step because this is the mistake to inoculate against: the visualization’s second prediction question asks what would happen without the save, and the correct answer — “the rest of the list is lost, immediately” — is worth feeling in the fingers, not just knowing.

Where the picture breaks down: fingers suggest you could walk back and re-check. You cannot. A singly linked list has no way backwards — that is why we are reversing it — so the algorithm gets exactly one pass, no retries, and every write is final. The discipline that fact imposes is the actual thing being examined.

Loading…

A walkthrough you can check

Reverse 1 → 2 → 3 → 4.

1. Start: prev = null, curr = 1. Save next = 2. Flip: 1’s arrow points at null (it is becoming the tail). Advance: prev = 1, curr = 2.
2. Save next = 3. Flip: 2 → 1. The drawing now shows two arrows pointing left and one pointing right — the reversed prefix and the untouched suffix, meeting at curr.
3. Save next = 4. Flip: 3 → 2. Advance.
4. Save next = null. Flip: 4 → 3. Advance: prev = 4, curr = null — loop ends.

Return prev = 4. The list reads 4 → 3 → 2 → 1, and 1 — the old head — correctly ends with null. Two checks worth making by eye in the player: at every mid-loop pause, the arrows left of curr all point left and the arrows right of curr all point right (the invariant, visible); and the final wash lands on the last box, because the new head is the old tail — the answer to the pick-question, and to the classic bug of returning the wrong end.

The invariant

At the top of each iteration: every node before curr has its arrow flipped and is reachable from prev in reversed order; every node from curr onward is untouched and reachable from curr in original order; and the two segments are disjoint. Initially trivial (prev’s segment is empty). Each iteration maintains it by construction: the save preserves reachability of the suffix, the flip moves exactly one node from the untouched segment to the reversed one, and the advance re-establishes the split point. When curr = null the untouched segment is empty, so the whole list is the reversed segment — correctness, with no case analysis.

Note what the invariant quietly rules out: no node is ever in both segments (no cycles created) and none in neither (no orphans) — the two failure modes of pointer surgery, both excluded by an invariant you can check visually at any pause.

Complexity, derived

The loop body runs once per node — one save, one write, three pointer assignments — and nothing else touches the list: O(n) time, O(1) space, and exactly n next-pointer writes (the unit suite counts them: flips = n, not n−1, because the old head’s null counts). This is optimal in every dimension: you cannot reverse without visiting every node, and you cannot beat three variables.

The recursive alternative — recurse to the tail, then flip on unwind — matches the O(n) time and reads beautifully, but spends O(n) stack, which on a million-node list is a stack overflow wearing elegant clothes. Its one legitimate use is interviews that explicitly ask for it; know it, then say why the loop is what ships.

What people get wrong

• The orphaned tail: flipping before saving. The single defining bug of this problem — everything after curr becomes unreachable the instant curr.next = prev runs.
• Returning head instead of prev: the function then hands back the old head — now the tail — and the caller sees a one-element list. The pick-question drills the right answer: the old tail is the new head.
• A loop at the seam: forgetting that the old head must end with null. If prev starts as anything but null, the “reversed” list’s last node points somewhere, and iteration never terminates.
• Losing the walk in a doubly linked list: with prev-pointers available the problem changes shape (swap next/prev per node); using the singly-linked routine unmodified leaves the prev chain stale.
• Off-by-one in k-group variants: reversing k nodes is this loop with a counter; the bug budget lives in reconnecting block boundaries, so write the stitch-up as its own step, not inline cleverness.

Implementation notes

The production form is the displayed loop, verbatim — it is already minimal. Two style points that pay: name the third variable next (or savedNext), never reuse a loop temp, because its entire purpose is to be readable insurance; and return prev, commenting why, because the maintainer after you will “fix” it to head otherwise.

For reverse-between (positions m to n): walk to m−1, run this loop n−m+1 times, then stitch — the node before the window connects to prev, and the window’s old first node (now its last) connects to curr. Doing the stitch with a dummy pre-head node removes the m=1 special case; the dummy-node trick is the general anaesthetic for head-mutation surgery and worth internalising here, on the simplest possible patient.

Testing pointer surgery deserves its own note: assert not just the values order but the termination (last node’s next is null) and, on the composites, node identity preservation — a reversal must move no values, only arrows. This site’s property test walks the reversed scene and compares against the reversed input for exactly that reason.

The follow-up questions

Why save next before the flip? curr.next is the only route to the unprocessed remainder; the flip overwrites it. Save-then-flip is the difference between an algorithm and a data-loss incident.

Recursive version — how, and what does it cost? Recurse to the end, then on each unwind: node.next.next = node; node.next = null. Same O(n) time, O(n) stack — elegant, and the wrong choice for long lists.

How does reverse-in-k-groups build on this? Reverse each block with this exact loop, then stitch blocks: the previous block’s tail (its old head) points at the new block’s head. The reversal is the easy half; the boundary bookkeeping is where the difficulty actually lives.

What changes for a doubly linked list? Per node, swap next and prev; the old swap-two-fields loop needs no third finger because prev-pointers preserve the way back. The singly linked version is harder precisely because the structure gives you nothing for free — which is why it is the one that gets asked.