Floyd's Cycle Detection algorithm (the "tortoise and hare") uses two pointers moving at different speeds. The slow pointer advances one step at a time; the fast pointer advances two steps. If a cycle exists, the fast pointer will eventually catch up to the slow pointer inside the cycle. The algorithm runs in O(n) time with O(1) space.
bool hasCycle(Node* head) {
Node* slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}The slow pointer moves one step at a time, the fast pointer two steps. If no cycle exists, fast reaches the end. If a cycle exists, fast laps slow — they must meet inside the cycle.
Once both pointers enter the cycle of length L, the relative speed between them is 1 step per iteration. They will meet within at most L iterations after fast enters the cycle.
After detecting the meeting point, reset slow to head. Advance both slow and the meeting pointer one step at a time. They will meet exactly at the cycle entry point — a beautiful mathematical result.
Cycle detection applies beyond linked lists: detecting loops in functional sequences, finding duplicate numbers in O(1) space (Floyd applied to arrays), and detecting infinite loops in state machines.
Quiz coming soon for this algorithm.