The problem with a loop#
Every list walk you have written so far ends the same way: keep going until next is nothing. If one node points back at an earlier one, that never happens. The walk runs for ever, and the program does not crash, it hangs, which is worse.
The obvious fix, and its cost#
Remember every node you visit in a set. If a node turns up twice, there is a loop.
That works and it is easy to get right. It costs memory proportional to the length of the list, and it needs the nodes to be hashable, which in C means comparing addresses by hand.
There is a way that uses two variables.
Two walkers#
Send a slow walker one step at a time and a fast walker two steps at a time.
If the list ends, the fast walker reaches the end first. No loop.
If the list loops, the fast walker can never reach an end, because there is none. Both end up inside the loop going round. Every step, the fast walker gains exactly one position on the slow one, so the gap between them shrinks by one each step: 3, 2, 1, 0. It cannot skip past, because it never changes by more than one. So they land on the same node, and that meeting is the proof.
That "gains exactly one per step" is the whole argument, and it is worth being able to say out loud.
Four questions, one technique#
Is there a loop? They meet, or the fast one finds an end.
How long is the loop? The meeting point is inside the loop, because neither walker can leave one. Stand there and walk one lap back to the same node, counting.
Where does the loop begin? Move one walker back to the head and step both at one speed. They meet at the start.
How do you cut it? Find the start, then walk round to the node whose next points at it. Clear that one link.
Why moving back to the head works#
This is the step that looks like a trick. Let a be the steps from the head to the start of the loop, b the steps from there to the meeting point, and c the rest of the loop.
When they meet, the slow walker has taken a + b steps and the fast one twice that. The fast one also went round the loop a whole number of times:
2(a + b) = a + b + k(b + c)
a + b = k(b + c)
a = k(b + c) - b
The last line says that a steps from the meeting point goes round the loop k whole times and then stops b short, which is exactly the start. And a steps from the head is the start by definition. So two walkers at the same speed, one from each place, arrive together. Neither of them ever needs to know what a is.
Where else the two walkers turn up#
The same pair, at the same speeds, finds the middle of a list in one pass: when the fast walker reaches the end, the slow one is halfway. And Floyd's method is not really about lists at all. It detects a repeat in any sequence where each value decides the next, which is why it also turns up in find the duplicate number, where the array indices form the links.
Practice in order#
- Does this list loop, for the pair on its own.
- How long the loop goes round, using the meeting point as a foothold.
- Where the loop begins, which is the algebra above.
- Break the loop, which is the same walk plus one link.
- The middle of a linked list, to see the same two walkers answering a different question.