Tortoise and Hare: Cycle Detection with Fast & Slow Pointers
When traversing a Linked List, how do you know if you are stuck in an infinite loop? Storing visited nodes in a Hash Set works, but it costs O(N) memory. Floyd's Cycle Finding Algorithm solves this mathematically using zero extra memory.
Introduction
The Fast and Slow Pointers pattern (also known as Floyd’s Tortoise and Hare algorithm) is a classic computer science technique used heavily in Linked List and Array problems.
The premise is simple: If two runners are racing on a circular track, and one is running twice as fast as the other, the faster runner will eventually lap the slower runner and they will collide. If the track is a straight line, the fast runner will simply cross the finish line.
The Mechanics
We initialize two pointers at the start of our data structure:
- Slow (The Tortoise): Moves forward exactly one node at a time.
- Fast (The Hare): Moves forward exactly two nodes at a time.
As we iterate:
- If there is no cycle, the
fastpointer will eventually hitnull(the end of the list), proving the list is linear. - If there is a cycle, the
fastpointer will loop around and crash into theslowpointer from behind. The momentslow == fast, we immediately returntrue.
Beyond Cycle Detection
This pattern isn't just for finding loops. It is an incredibly versatile mathematical tool.
Finding the Middle of a Linked List
If you want to find the exact middle node of a Linked List (often required for Merge Sort on lists), you can use this exact pattern.
By the time the fast pointer reaches the very end of the list, the slow pointer will be sitting exactly in the middle! This allows you to find the midpoint in a single pass without having to count the total length first.
Complexity Analysis
- Time Complexity: $O(N)$ — If there is no cycle, we traverse the list once. If there is a cycle, the fast pointer will lap the slow pointer in proportional time to the cycle length.
- Space Complexity: $O(1)$ — We are only allocating two pointer variables, making this infinitely more efficient than keeping a
HashSetof visited nodes.
Implementation
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == 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 (slow == fast) {
return true; // They collided!
}
}
return false; // Fast reached the end, no cycle.
}
}