Cycle Detection
Overview
Also known as Floyd's Tortoise and Hare Algorithm, this is a legendary, mind-bending application of the Two Pointers pattern.
Imagine traversing a singly linked list. If the tail node accidentally points back to a middle node, it creates a cycle (an infinite loop). If you try to traverse it, your program will spin forever. How do you detect this in O(N) time and strictly O(1) memory? (Using a HashSet to track visited nodes takes O(N) memory, which violates strict space constraints).
You create two pointers. The slow pointer (Tortoise) moves 1 step at a time. The fast pointer (Hare) moves 2 steps at a time.
If there is NO cycle, the fast pointer will harmlessly hit null and terminate.
If there IS a cycle, they will both enter the loop. Because the fast pointer moves exactly 1 step faster relative to the slow pointer, it will mathematically lap the slow pointer and eventually fast == slow. This definitively proves a cycle exists without storing any data.
Syntax
public class LinkedListCycle {
static class ListNode {
int val; ListNode next;
}
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head;
// Fast must check its next jump to avoid NullPointerException
while (fast != null && fast.next != null) {
slow = slow.next; // Tortoise moves 1 step
fast = fast.next.next; // Hare moves 2 steps
if (slow == fast) {
return true; // The hare lapped the tortoise. Cycle exists!
}
}
return false; // Hare reached the end safely. No cycle.
}
}Common Pitfalls
- NullPointerException when checking
fast.next.next. Iffast.nextis null, calling.nexton it crashes. The while loop conditionwhile (fast != null && fast.next != null)is strictly mandatory to prevent this. - Starting pointers at different locations incorrectly. Standard practice starts both at
head. If you startslowatheadandfastathead.next, the logic still works, but your math for finding the start of the cycle later will be off by one. - Using it for Non-Linked List problems blindly. This pattern strictly relies on traversal structures where you can jump 'next'.
Interview Questions
This is a famous extension (Cycle Detection II). Once slow and fast meet, you leave fast where it is, and reset slow back to the head. Then, you move BOTH pointers at the same speed (1 step at a time). The exact node where they collide again is the start of the cycle. (This is proven by the math of the distance traveled).
Use Fast and Slow pointers! When the fast pointer reaches the end of the list, the slow pointer will be sitting exactly on the middle node.
Real-World Example
Infinite loop detection in state machines or network routing. If a networking protocol accidentally creates a routing loop, packets will bounce between routers infinitely. Fast/Slow pointer logic can be adapted in stream processing to detect recurring cyclical states without consuming massive amounts of memory tracking every packet's history.
// Conceptual State Machine validation
public boolean validateStateMachine(State start) {
State slow = start;
State fast = start;
while (fast != null && fast.nextState() != null) {
slow = slow.nextState();
fast = fast.nextState().nextState();
if (slow == fast) {
log.error("Fatal: State Machine contains an infinite loop!");
return false;
}
}
return true;
}Check Your Knowledge
Test your understanding of Cycle Detection with these quick questions.