A linked list is boxes and arrows, and every list problem is rewiring arrows without dropping the chain. Add one extra idea — two runners at different speeds — and middles, cycles, and nth-from-the-end all fall in O(1) space.
Linked-list problems are the interview's pointer-discipline exam. There's no clever math here, no deep theory — just boxes, arrows, and the question of whether you can re-route the arrows without ever letting go of the only rope that leads to the rest of the list. That, plus one genuinely beautiful trick: two runners at different speeds, which turns "find the middle" and "is there a cycle?" into O(1)-space one-liners.
The whole chapter is about six moves: the three-pointer reversal, the dummy head, the zipper merge, the fast-slow pair, the fixed gap, and the hash-map-plus-list combo. Every canonical list problem — and there are surprisingly few — is these moves, alone or chained.
An array is a row of houses on one street: to visit house 4,217 you jump straight there, because the address is arithmetic. A linked list is a scavenger hunt: each box holds a value and one arrow to the next box, and the only way to reach box 4,217 is to follow 4,216 arrows. That single design choice sets every cost in the structure:
Interviewers reach for lists not because your job involves hand-rolled lists (it almost certainly doesn't) but because list problems are impossible to fake. Off-by-one errors, null checks, aliasing — either your pointer hygiene is real or the whiteboard exposes it in four lines. The good news: the question bank here is tiny and extremely canonical. Reverse Linked List Easy, Merge Two Sorted Lists Easy, Linked List Cycle Easy, Middle of the Linked List Easy, Remove Nth Node From End of List Medium, Reorder List Medium, LRU Cache Medium. Learn six moves, and that entire roster is reruns.
Reverse Linked List Easy is the drosophila of list problems: small, endlessly studied, and carrying the entire genome. The task: make every arrow point the other way, using no extra memory. The move is the three-pointer shuffle, and it maintains one crisp invariant: prev is the head of the already-reversed part, curr is the head of the untouched part, and the list is always exactly those two pieces — nothing is ever lost.
Each loop iteration moves one node across the border, in four beats: save the rest (nxt = curr.next), flip the arrow (curr.next = prev), and advance both names (prev = curr; curr = nxt). When curr walks off the end, prev is standing on the new head. O(n) — one visit per node; O(1) space — three names, zero copies. Step it yourself:
Half of all ugly list code comes from one special case: the head is different. Deleting the head, inserting before the head, building a result list from nothing — each wants an if that the rest of the list doesn't need. The fix costs one line: allocate a throwaway node, the dummy head, and hang your real list off it. Now every node — including the real head — has a predecessor, every operation is the general case, and the answer is always dummy.next. It is the cheapest elegance purchase in this book.
The dummy head's signature appearance is Merge Two Sorted Lists Easy — the zipper. Keep a tail pointer starting at the dummy; repeatedly compare the two list heads, stitch the smaller one onto tail, and advance into the list you took from. When one list runs dry, attach the survivor whole — it's already sorted, no loop needed. O(n + m) — every node gets touched once, and no new nodes are made: you're re-wiring the ones you were given.
File the shape away, because it scales: merging k sorted lists is the same zipper with k teeth, and choosing the smallest of k heads efficiently is exactly what a heap is for — Merge K Sorted Lists Hard is waiting for you in Chapter 14, and it's this section plus one data structure.
Here's the chapter's one genuinely magic trick. A linked list gives you no length, no indices, no way to jump — just "next". So how do you find the middle in one pass? Send two runners from the head: slow takes one step per tick, fast takes two. When fast runs off the end, it has covered the whole list — which means slow, at exactly half its speed, is standing on the middle. That's Middle of the Linked List Easy, solved with two pointers and zero arithmetic.
Now the better question: what if the list has a cycle — some node's arrow points backwards, and "next" never ends? You can't watch for null; there isn't one. You could remember every node you've visited in a hash set (Chapter 4 reflex — it works, O(n) space), but the follow-up is always "now do it in O(1) space". Same two runners: if there's a cycle, fast enters it first, laps the track, and must eventually land on slow. If there's no cycle, fast hits null and you're done. This is Floyd's cycle detection — Linked List Cycle Easy — and phase two below even finds where the cycle starts. Race them:
Interviewers love asking "why does that work?" — and the proof is short enough to say out loud. Phase 1: once both runners are inside a cycle of length c, think of the gap between them, measured around the track. Each tick, slow moves 1 and fast moves 2, so the gap shrinks by exactly 1 (mod c). A gap that shrinks by one each tick on a finite track hits zero within c ticks. No leaping over, no near misses — the hare closes on the tortoise like a zipper. Meeting guaranteed, in O(n) total steps.
Phase 2 is the part people half-remember, so own the reasoning: say the tail (head to cycle start) has length t, and the runners meet m steps into the cycle. Slow has walked t + m; fast has walked twice that, 2(t + m); the difference, t + m, must be whole laps of the cycle. Rearranged: walking t more steps from the meeting point lands exactly on the cycle start — the same distance as walking t from the head. So: reset one runner to the head, march both at speed 1, and the node where they collide is the cycle start. That's Linked List Cycle II, and it's also the trick behind Find the Duplicate Number Medium — an array problem where i → nums[i] secretly draws a linked list with a cycle. Costumes, as always.
Fast-slow has a sibling where both runners move at the same speed but start apart. Remove Nth Node From End of List Medium: you can't count from the end of a singly linked list — the arrows only go forward — and the obvious fix (walk once to measure the length, walk again to the right spot) takes two passes. One pass: send a scout pointer n steps ahead, then walk scout and trailer together. The gap between them stays frozen at n, so when the scout steps off the end, the trailer is standing exactly n from it — right where you need to be. Start the trailer at a dummy head (§3, told you it recurs) so it stops just before the victim, and deletion is one rewire: trailer.next = trailer.next.next.
And then there are the combo problems, where the moves chain. Reorder List Medium ("fold the list: first, last, second, second-to-last…") looks novel and is actually a three-course meal of this chapter: fast-slow to find the middle (§4), three-pointer shuffle to reverse the back half (§2), zipper merge to interleave the two halves (§3). No new ideas — just recognition, three times in a row. Most Medium/Hard list problems decompose exactly like this, which is why the six moves are worth drilling to reflex.
LRU Cache Medium is the most-asked design problem in the bank, and it's this chapter's graduation exercise. The contract: get(key) and put(key, value), both O(1), with a fixed capacity — and when the cache is full, evict the least recently used entry. Read that as two requirements that no single structure satisfies: find by key instantly (a hash map's whole personality, Chapter 4) and maintain a usage ordering you can edit instantly — move-to-front on every touch, evict-from-back when full. Arrays shift in O(n); heaps reorder in O(log n); only a linked list re-chains a node in O(1).
So you weld them together: a doubly linked list ordered most-recent → least-recent, and a hash map from key to the list node itself. Every get hits the map, then unlinks the node and re-chains it at the front. Every put inserts at the front and, on overflow, snips the back node off — the map tells you where things are, the list tells you how stale they are. Two structures, each covering the other's weakness. Drive one:
Recognition here is easy — the problem literally says "linked list" — so the skill shifts one level down: hearing which move the problem wants. Run the mapping: mutation in place → the shuffle (§2); the head might change → dummy (§3); two sorted lists → zipper (§3); middle, cycle, or an O(1)-space demand → fast-slow (§4–5); "from the end" in one pass → the gap (§6); O(1) operations on a changing order → hash + doubly linked (§7). Anything fancier is a chain of those, and saying the decomposition out loud ("middle, then reverse, then merge") is worth more than silently coding it.
Two habits close out the chapter. First, draw before you code — every list bug in existence is visible in a boxes-and-arrows sketch and invisible in text. Second, test the degenerate lists: empty, one node, two nodes. Fast-slow code in particular loves to dereference fast.next.next when fast.next is already null — the single most common runtime error in this problem family, and one a two-node trace catches every time.
The pattern, as a whiteboard skeleton:
The flagship is Reverse Linked List Easy — partly because it's the most-asked list question in existence, mostly because its loop body is the chapter: save, flip, advance. Read the invariant, not the lines: at the top of every iteration, prev heads a correctly reversed prefix and curr heads the untouched suffix, and the loop just moves the border one node to the right.
The Scala tab carries the aside worth savoring: written tail-recursively, the two accumulators (prev, curr) make it obvious that reversal is a left fold — each step peels one element off the input and conses it onto an accumulator. The imperative shuffle and foldLeft(Nil)((acc, x) => x :: acc) are the same algorithm; the pointers are just what a fold looks like when the cells are mutable. One idea, two costumes — which, by now, is the book's whole refrain.