List Pointer Puzzles
A singly linked list can only be walked forwards, one node at a time, so the classic puzzles are all about walking cleverly instead of storing things. To read a list backwards, reverse half of it in place and put it back afterwards. To find where two lists merge without measuring them, let each pointer walk its own list and then the other one: both cover the same total distance and arrive at the shared node together. To remove a cycle, the slow and fast meeting point plus a walk from the head lands on the loop's entry, and one lap round the loop finds the arrow to cut. Each is O(n) time with a constant number of pointers.
Is the list the same read backwards? A list cannot be read backwards, so make half of it readable that way: find the middle, reverse the second half in place, walk the two halves together comparing values, then reverse the half back so the list is left as it was.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 4, with their answers.
With 5 nodes, which node does slow stop on?
Answer: 3. Slow has moved half as far as fast, which covered the whole list.
Next pair: 1 from the front and 1 from the back. Equal?
Answer: Equal. Each front node is checked against the node the same distance from the end.
Next pair: 2 from the front and 2 from the back. Equal?
Answer: Equal. Each front node is checked against the node the same distance from the end.
Next pair: 3 from the front and 3 from the back. Equal?
Answer: Equal. Each front node is checked against the node the same distance from the end.
How it runs, step by step
Is the list the same read backwards? A list cannot be read backwards, so make half of it readable that way: find the middle, reverse the second half in place, walk the two halves together comparing values, then reverse the half back so the list is left as it was.
Checking whether 1, 2, 3, 2, 1 is a palindrome.
Slow takes one step for every two of fast. When fast runs out, slow is at 3, the start of the second half, which includes the middle node; comparing it with itself is harmless.
Second half starts at 3.
Reverse the second half: 3 now points at null.
3 points at null.
Reverse the second half: 2 now points at 3.
2 points at 3.
Reverse the second half: 1 now points at 2.
1 points at 2.
Compare 1 from the front with 1 from the back: equal, keep going.
1 against 1: equal.
Compare 2 from the front with 2 from the back: equal, keep going.
2 against 2: equal.
Compare 3 from the front with 3 from the back: equal, keep going.
3 against 3: equal.
Reverse the second half again so the list reads 1, 2, 3, 2, 1 as before. Verdict: every pair matched, a palindrome.
List restored. Palindrome.
A palindrome. 3 comparisons, two half reversals, O(n) time and O(1) extra space; copying the values into an array would be simpler but costs O(n) memory.
Palindrome.
Write it yourself
Define isPalindromeList(values) and return true when the list reads the same in both directions. It runs in your browser against this lesson's own 2 examples.
// Find the middle with a fast and a slow pointer, reverse the second half, and walk the two halves together.function isPalindromeList(values) { return false;}
Remember
- Palindrome: slow and fast to the middle, reverse the second half, compare front against back, reverse it back.
- Intersection: walk pa down A then B and pb down B then A; they meet at the shared node after lenA + lenB steps, or at null together.
- Remove cycle: after slow and fast meet, walk from the head and the meeting point together to the entry, then once round the loop to cut the arrow before it.
Where this is used
FilesystemsRepairing a FAT filesystem
On a FAT volume a file is literally a singly linked list: the directory entry names the first cluster and the file allocation table says which cluster follows each one. Corruption produces exactly these two puzzles, and fsck.fat lists both as things it fixes - a cluster chain that contains a loop, and two or more files that share the same clusters, which is two lists merging into a common tail. There is no way to jump into the middle of a file, so the chain is walked one link at a time and the loop has to be noticed before the walk becomes endless.
Operating systemsReversing the kernel's lockless list
Linux's llist is a lock-free singly linked stack: producers push with llist_add and a consumer takes the whole chain in one atomic swap. llist.h spells out what that costs - the entries come back newest first, and if you want to walk them oldest to newest you have to reverse the chain yourself. llist_reverse_order in lib/llist.c is exactly the three-pointer walk this lesson's reverse() does: hold the node, remember its next, point it back at the new head, move on. Callers can be in interrupt or NMI context, where allocating a scratch array to sort the chain into is not available, so the rewiring happens in place.
Distributed systemsBitcoin Core finding a fork point
A block header stores the hash of its parent, so a chain is a singly linked list that can only be walked backwards toward the genesis block. Before switching to a competing chain a node has to find the last block the two share, which is the intersection problem: Bitcoin Core's LastCommonAncestor drops the taller chain down to the other's height first and then steps both back in lockstep. That is the variant you use when the lengths are already known, and the head-swapping walk in this lesson is what you do when they are not.
Memory managementMarking a heap with no spare memory
A tracing collector normally marks live objects using an explicit stack of nodes still to visit, but a collector runs precisely when memory has run out, so that stack is the one thing it may not be able to afford. The Deutsch-Schorr-Waite algorithm reverses each pointer as it descends into an object, so the route back to the root is held in the heap itself, and puts every pointer back on the way up. That is the same move as reversing half a list to read it backwards and reversing it again to leave no trace, which is why early Lisp and embedded collectors used it.
Why it works this way
Why the intersection walk has to step through null
Each pointer walks one list and then the other, so both cover the same total distance, and the null at the end of each list counts as one of those steps. The classic bug is to write the switch as "if the next node is null, jump to the other head", which skips null entirely: two lists that never merge then chase each other forever, because the pointers are only ever equal at a shared node and there is none. Landing on null is what lets both pointers be null on the same step, and null matching null is what ends the loop.
Why walking from the head lands on the loop's entry
Call L the number of steps from the head to the entry, C the length of the loop, and say the pointers meet k steps into it. Slow has walked L + k and fast exactly twice that, and fast's extra distance is a whole number of laps, so L + k = mC and therefore L = mC - k. The distance forward from the meeting point round to the entry is C - k plus m - 1 more laps, which is the same mC - k. The two walks are the same length, so a pointer from the head and a pointer from the meeting point arrive together.
The palindrome check leaves the list broken while it runs
Reversing the second half rewires real nodes: mid-check the middle node's next is null and the back half runs the other way, which is why the code reverses a second time instead of just returning. It is also why the compare loop is driven by second rather than first. The front half still runs into the reversed region and is never the shorter of the two, so stopping when first runs out reads second one step after it has already hit null on an even-length list. If anything else can see the list while this runs, copy the values into an array instead.
Why the cycle loop is a do-while, and why fast steps by two
slow and fast both start at the head, so a plain while (slow !== fast) would exit before either has moved; the do-while forces the first step. A stride of two makes the gap between the pointers shrink by exactly one node per round once both are inside the loop, so it has to reach zero and they cannot step over each other. A stride of three shrinks the gap by two, and on a loop of even length with an odd gap that never reaches zero. Both levels of fast.next?.next need the null check: guarding only one crashes at the end of a cycle-free list with an odd number of nodes.
Read more
- Cycle detectionWikipedia
- Tortoise and hare algorithmcp-algorithms
- fsck.fat(8): loops and shared clusters in a chainman7.org
- lib/llist.c: llist_reverse_orderLinux kernel · git.kernel.org
- LastCommonAncestor in Bitcoin Core's chain.cppbitcoin/bitcoin · github.com
- Linked listWikipedia