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.
The last node points back to 3, so walking this list never ends. Detect a loop with slow and fast; if they meet, find the loop's entry by walking from the head and the meeting point together; then walk once round the loop to the node before the entry and cut its arrow.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.
Slow moves one and fast moves two. Do they land on the same node?
Answer: No, not yet. Inside a loop fast gains one node on slow every step, so it must catch up eventually.
Slow moves one and fast moves two. Do they land on the same node?
Answer: No, not yet. Inside a loop fast gains one node on slow every step, so it must catch up eventually.
Slow moves one and fast moves two. Do they land on the same node?
Answer: No, not yet. Inside a loop fast gains one node on slow every step, so it must catch up eventually.
Slow moves one and fast moves two. Do they land on the same node?
Answer: Yes, they meet. Inside a loop fast gains one node on slow every step, so it must catch up eventually.
The loop enters at 3. Which node's arrow must be cut?
Answer: 6. The node whose next points back at the entry closes the loop.
How it runs, step by step
The last node points back to 3, so walking this list never ends. Detect a loop with slow and fast; if they meet, find the loop's entry by walking from the head and the meeting point together; then walk once round the loop to the node before the entry and cut its arrow.
Removing a cycle from 1, 2, 3, 4, 5, 6.
Slow to 2, fast to 3. Not the same node yet.
Slow 2, fast 3.
Slow to 3, fast to 5. Not the same node yet.
Slow 3, fast 5.
Slow to 4, fast to 3. Not the same node yet.
Slow 4, fast 3.
Slow to 5, fast to 5. They meet, so the list loops. Slow stays here as the meeting point.
Slow and fast meet at 5.
p from the head and slow from the meeting point step together: p at 2, slow at 6. Not yet.
p 2, slow 6.
p from the head and slow from the meeting point step together: p at 3, slow at 3. They meet: 3 is where the loop begins.
Entry found at 3.
The entry is 3. Walk once round the loop from it to the node whose next is the entry: 6. Its arrow is the one that closes the loop.
Loop closes at 6.
Set 6's next to null. The list now ends there and reads 1, 2, 3, 4, 5, 6.
Cycle removed. List reads 1, 2, 3, 4, 5, 6.
Cycle removed with three pointer walks, each at most n steps: O(n) time, O(1) space, and no node was marked or stored to do it.
Result 1, 2, 3, 4, 5, 6.
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