Sign in to watch this lesson
Algorithms - Linear Data Structures · 4:17
Floyd's Cycle Detection
A list whose last pointer leads back inside itself never reaches null. Floyd's tortoise and hare race on the rho 0 to 7 (tail 3, loop 5) and meet at node 5; the equation a = L - b then says that restarting one runner at the head and stepping both once lands them together on the entry, node 3, and one more lap gives the loop length. The same O(1)-memory trick works on any sequence x -> f(x): Find the Duplicate, and a pseudo-random generator measured on this Mac against a hash map of first visits.
You will learn
- Detect a cycle in a linked list (or any sequence x -> f(x)) with two pointers moving at speeds one and two, in O(mu + lambda) time and O(1) memory
- Prove that the pointers meet inside the loop within one lap, and derive a = kL - b to find the loop's entry by restarting one pointer at the head
- Measure the loop length with one more lap, and apply the method to Find the Duplicate and to the period of a pseudo-random generator
- Avoid the classic bugs: missing null checks on the fast pointer and starting the two pointers at different nodes