Fast and Slow Pointers
A list has no index, so you cannot jump to the middle or the end. Two pointers moving at different speeds get you there anyway, in one pass and with no counting.
The last node points back to 4, so this list loops. Does the list loop? Slow moves one, fast moves two. On a straight list fast runs off the end. On a loop, fast keeps lapping until it lands on slow.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 7, with their answers.
Slow is at 2, fast is at 3. Next?
Answer: Keep going. Not yet. Fast is still ahead.
Slow is at 3, fast is at 5. Next?
Answer: Keep going. Not yet. Fast is still ahead.
Slow is at 4, fast is at 7. Next?
Answer: Keep going. Not yet. Fast is still ahead.
Slow is at 5, fast is at 5. Next?
Answer: They meet. Same node, so the list loops.
One step each. Do they land on the same node?
Answer: Not yet. Still different nodes, so keep walking.
One step each. Do they land on the same node?
Answer: Not yet. Still different nodes, so keep walking.
One step each. Do they land on the same node?
Answer: Yes, that is the entry. Equal distances, so they meet exactly at the entry.
How it runs, step by step
The last node points back to 4, so this list loops. Does the list loop? Slow moves one, fast moves two. On a straight list fast runs off the end. On a loop, fast keeps lapping until it lands on slow.
Detecting a cycle with slow and fast pointers.
Step 1: slow to 2, fast to 3.
Slow is at 2 and fast at 3.
Step 2: slow to 3, fast to 5.
Slow is at 3 and fast at 5.
Step 3: slow to 4, fast to 7.
Slow is at 4 and fast at 7.
Step 4: slow to 5, fast to 5. Same node. Fast lapped slow, which only a loop allows.
Slow is at 5 and fast at 5. They have met.
Now find where the loop starts. Send one pointer back to the head and leave the other where they met. Walk both one node at a time: the distance from the head to the entry equals the distance from the meeting point round to the entry, so they arrive together.
One pointer returns to the head; both now move one step at a time.
Both step once: 2 and 6.
The pointers are at 2 and 6.
Both step once: 3 and 7.
The pointers are at 3 and 7.
Both step once: 4 and 4. Same node. This is where the loop begins.
The pointers are at 4 and 4. They meet at the cycle entry.
The loop starts at 4, index 3, found in 3 more steps.
The cycle begins at 4.
Write it yourself
Define middleIndex(values) and return the position of the middle node, counting from 0, taking the second of two. It runs in your browser against this lesson's own 2 examples.
// Move one pointer one step and the other two. When the fast one runs out, the slow one is in the middle.function middleIndex(values) { return 0;}
Remember
- When fast runs out, slow is at the middle. When fast lands on slow, the list loops.
- After the pointers meet in a loop, restart one at the head and walk both by one to find the entry.
- A fixed gap between two pointers finds the nth from the end without knowing the length.
Topics covered
Where this is used
CryptographyPollard's rho factorisation
Pollard's rho factors an integer by iterating x -> x * x + c mod n until the sequence repeats, because the repeat is what exposes a factor through a gcd. Nothing is stored: the walk is expected to run for about the fourth root of n steps before it comes back on itself, already ten billion values for a 40-digit n, so the repeat has to be caught with a few registers rather than a table. Pollard used the two-speed walk for that. GNU coreutils' factor ships the same algorithm with Brent's variant of the cycle search, which holds one saved value and compares against it over runs of doubling length instead of stepping a second cursor.
Systems librariesSplitting a list in GLib's sort
g_list_sort walks a GList with two cursors, advancing one by a single node for every two the other takes, then cuts the list where the slow cursor stopped and merge sorts the two halves. A GList carries no length field, so counting the nodes first would mean an extra full traversal at every level of the recursion. The fast cursor starts one node ahead and takes both of its steps before the slow cursor takes any, which is how the split lands on the earlier middle rather than the later one.
SimulationMeasuring a random generator's period
A pseudorandom generator is a pure function from state to state, so its output must eventually repeat, and how long that takes is the property you check before seeding a simulation with it. For a small-state generator such as an LCG or xorshift32 the period runs into billions, far too long to store the stream and look for a duplicate, yet two copies of the generator, one stepped twice for every single step of the other, measure it exactly in two words of memory. It is also how a generator seeded into a short orbit gets caught before it quietly repeats itself a few thousand draws in.
Developer toolsReading the end of a stream you cannot rewind
tail -n 5 on a pipe cannot seek backwards and does not know how many lines are coming, which is the same shape as removing the nth node from the end of a list. The answer is the same too: keep a second cursor a fixed n behind the one doing the reading, so the moment the lead hits the end the trailing one is already parked on the node you want. Python's collections.deque(maxlen=n) is that fixed gap turned into a data structure.
Why it works this way
Why two steps and one, and not three and one?
With fast on two and slow on one, the distance between them changes by exactly one every step, so once both are inside the loop that distance has to pass through zero and the pointers land on the same node within a single lap, wherever each of them started. Three steps to one changes the distance by two, and that can step over zero forever: start fast one node ahead, a common variant of the setup, and the gap stays odd, so on a loop of even length the two pointers never meet. Starting both at the head happens to avoid that case, but a second reason survives it. Finding the loop entry needs fast to have walked exactly twice as far as slow, and at three steps to one the meeting point no longer sits where that argument puts it.
Why restarting at the head lands exactly on the entry
Call the run-up before the loop m nodes and the loop itself L nodes, and say the pointers meet k steps into the loop. Slow has walked m + k, fast has walked twice that, and fast's extra distance is a whole number of loops, so m + k is a multiple of L. Walking m more steps from the meeting point therefore lands back on the entry, which is why a pointer released from the head and a pointer released from the meeting point, both moving one step at a time, collide there and nowhere else.
On an even list this returns the second middle
For six nodes the loop above stops with slow on index 3, the later of the two middles. Testing fast.next and fast.next.next instead stops it on index 2, the earlier one. The difference matters when you split a list for merge sort as head..slow and slow.next..end: with the later middle a two-node list splits into the whole list plus an empty one, the recursion never shrinks, and it runs forever. The same condition is also the null guard, because on even lengths fast becomes null rather than landing on a final node, and code that checks fast alone and then reaches for fast.next.next is the usual crash.
Why not just remember every node you have seen?
A set of visited nodes finds the loop in one pass too and is easier to argue about. It costs a slot per node, which is fine for a list you already hold in memory and useless everywhere else. When the sequence is produced by a function rather than stored, such as a generator's state or x -> x * x + c mod n, there are no node identities to put in a set and the space of states is far too large to keep any part of. The two-pointer version is the one that survives when the data is generated instead of held.
Read more
- Cycle detectionWikipedia
- Floyd's linked list cycle finding algorithmcp-algorithms
- Pollard's rho algorithmWikipedia
- An improved Monte Carlo factorization algorithmR. P. Brent, BIT 20 (1980) · maths-people.anu.edu.au
- g_list_sort in GLibGNOME GLib source · gitlab.gnome.org