Topic 77 of 78
Cycle Detection
Overview
Floyd's Cycle Detection Algorithm (often called Fast & Slow Pointers or the Tortoise and Hare) is an incredibly clever pointer algorithm. You use two pointers: a slow one that moves 1 step at a time, and a fast one that moves 2 steps at a time. If there is a loop/cycle in the Linked List (or array), the fast pointer will eventually 'lap' the slow pointer and they will point to the exact same node. It detects cycles in O(N) time using purely O(1) space.
Syntax
By moving at different speeds, if a cycle exists, the fast pointer loops around and catches the slow pointer from behind.
Detecting a Linked List Cycle
java
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // Moves 1 step
fast = fast.next.next; // Moves 2 steps
// If they ever meet, there is a cycle!
if (slow == fast) {
return true;
}
}
return false; // Fast hit the end of the list, no cycle.
}Common Pitfalls
- NullPointerExceptions! Because `fast` jumps 2 steps at a time, you must strictly verify `fast != null` AND `fast.next != null` in your while loop condition.
Interview Tips
- This is the ONLY acceptable way to find a cycle in O(1) space. Using a HashSet to track visited nodes takes O(N) space and will fail the optimal constraints of the interview.
Real-World Example
Detecting infinite loops or deadlocks in state machines, routing algorithms, or memory reference cycles in garbage collectors.
example
java
// Fast & Slow pointers are a staple of memory leak detection algorithms.