Detecting the loop
Floyd's cycle detection uses a slow pointer moving one step and a fast pointer moving two steps. If the sequence eventually cycles, the fast pointer wraps around and collides with the slow one inside the loop. If it never cycles, the fast pointer escapes off the end. This uses only two pointers and no extra memory.
Finding the loop start
The elegant part is locating the entry node of the cycle after a collision. Reset one pointer to the start and leave the other at the meeting point, then advance both one step at a time. They meet exactly at the cycle entrance.
This works because of a distance identity: the gap from the start to the entry equals the gap from the meeting point back around to the entry, so two single speed walkers arrive together.
Where it is used
- Linked lists, to test for and find a loop.
- Functional iteration, where each value maps to a next value.
- Duplicate finding, by treating array values as next pointers.
Key idea
Floyd's method finds a cycle with two pointers at one and two speeds, then uses a distance identity to walk two single speed pointers to the exact cycle entry, all without extra memory.