Floyd's Algorithm: Cycle Detection and Entry Point
Cycles in data structures cause real problems. A circular reference in a linked list creates an infinite loop when you traverse it. Memory management systems that can't detect cycles leak resources....
Key Insights
- Floyd’s algorithm detects cycles in O(n) time with O(1) space by using two pointers moving at different speeds—the fast pointer will always catch the slow pointer inside a cycle
- Finding the cycle entry point requires a second phase: reset one pointer to the head and move both at the same speed until they meet at the cycle start
- The algorithm extends beyond linked lists to any sequence with repeated values, making it useful for problems like finding duplicates in arrays
Introduction to Cycle Detection
Cycles in data structures cause real problems. A circular reference in a linked list creates an infinite loop when you traverse it. Memory management systems that can’t detect cycles leak resources. Serialization code that doesn’t handle cycles produces infinite output or stack overflows.
The problem appears everywhere: garbage collectors need to identify circular references, network routing algorithms must detect routing loops, and deadlock detection in operating systems requires finding cycles in resource dependency graphs.
The core question is simple: given a sequence of elements where each element points to the next, how do you determine if following these pointers eventually leads back to a previously visited element?
The Naive Approach and Its Limitations
The obvious solution uses a hash set. As you traverse the structure, store each visited node. If you encounter a node already in the set, you’ve found a cycle. If you reach the end (null), there’s no cycle.
def has_cycle_naive(head):
"""Detect cycle using hash set. O(n) time, O(n) space."""
visited = set()
current = head
while current is not None:
if current in visited:
return True
visited.add(current)
current = current.next
return False
This works correctly and runs in O(n) time. The problem is space complexity. You’re storing a reference to every node you visit, consuming O(n) memory. For a list with millions of nodes, that’s millions of stored references.
In memory-constrained environments or when processing massive datasets, this overhead becomes unacceptable. We need an algorithm that uses constant space regardless of input size.
Floyd’s Tortoise and Hare Algorithm
Robert Floyd developed an elegant solution in the 1960s. The insight: use two pointers moving at different speeds through the structure.
The “tortoise” moves one step at a time. The “hare” moves two steps at a time. If there’s no cycle, the hare reaches the end. If there’s a cycle, the hare eventually laps the tortoise—they meet inside the cycle.
Think of it like two runners on a circular track. The faster runner will eventually catch up to and pass the slower runner. They must meet.
class ListNode:
def __init__(self, val=0):
self.val = val
self.next = None
def has_cycle(head):
"""Floyd's cycle detection. O(n) time, O(1) space."""
if head is None or head.next is None:
return False
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next # Move one step
fast = fast.next.next # Move two steps
if slow == fast:
return True
return False
The space complexity drops to O(1)—just two pointer variables regardless of list size. Time complexity remains O(n) because the fast pointer traverses the list at most twice before either reaching the end or meeting the slow pointer.
Mathematical Proof: Why It Works
Understanding why the pointers meet requires some notation. Let’s define:
- μ (mu): Distance from the head to the cycle entry point
- λ (lambda): Length of the cycle
- k: Number of complete cycles the fast pointer makes before meeting
When the slow pointer enters the cycle (after μ steps), the fast pointer has traveled 2μ steps. The fast pointer is already somewhere inside the cycle, specifically at position (2μ - μ) mod λ = μ mod λ steps into the cycle.
Once both pointers are in the cycle, think of their relative motion. The fast pointer gains one position on the slow pointer with each step. Since the cycle has length λ, the fast pointer catches the slow pointer within λ steps after the slow pointer enters.
At the meeting point, let’s say the slow pointer has traveled distance d from the head:
- Slow pointer distance: d
- Fast pointer distance: 2d
Both are at the same position, so their distances differ by some multiple of the cycle length:
2d - d = k * λ
d = k * λ
This means the slow pointer has traveled exactly k complete cycles worth of distance when they meet. This relationship becomes crucial for finding the entry point.
Finding the Cycle Entry Point
Detecting a cycle is useful, but often you need to know where it starts. Floyd’s algorithm has a brilliant second phase.
After the pointers meet inside the cycle, reset one pointer to the head. Now move both pointers one step at a time. They will meet exactly at the cycle entry point.
Here’s why. When the pointers first meet, the slow pointer has traveled some distance d. We established that d = k * λ for some integer k.
The meeting point is d - μ steps into the cycle (total distance minus the distance to enter). Since d = k * λ, the meeting point is (k * λ - μ) steps into the cycle.
Now, if we move μ more steps from the meeting point, we travel:
(k * λ - μ) + μ = k * λ
That’s exactly k complete cycles—we end up at the cycle entry point.
Simultaneously, a pointer starting from the head and moving μ steps also reaches the cycle entry point. Both pointers travel the same distance and meet at the entry.
def detect_cycle_entry(head):
"""Find the node where the cycle begins. Returns None if no cycle."""
if head is None or head.next is None:
return None
# Phase 1: Detect if cycle exists
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow == fast:
# Cycle detected, proceed to phase 2
break
else:
# No cycle found
return None
# Phase 2: Find entry point
# Reset one pointer to head, move both at same speed
pointer1 = head
pointer2 = slow # The meeting point
while pointer1 != pointer2:
pointer1 = pointer1.next
pointer2 = pointer2.next
return pointer1 # This is the cycle entry node
Practical Applications
Beyond linked list cycle detection, Floyd’s algorithm solves problems that might not obviously involve cycles.
Finding Duplicate Numbers
LeetCode problem 287 asks: given an array of n+1 integers where each integer is between 1 and n inclusive, find the duplicate. The constraint: O(1) extra space, don’t modify the array.
The trick is recognizing the array as an implicit linked list. If nums[i] = j, treat it as node i pointing to node j. Since values are between 1 and n but we have n+1 elements, at least one value repeats—creating a cycle.
def find_duplicate(nums):
"""
Find duplicate in array where nums has n+1 elements
with values in range [1, n].
Treat array as implicit linked list:
index i -> index nums[i]
The duplicate value is the cycle entry point.
"""
# Phase 1: Find meeting point
slow = nums[0]
fast = nums[0]
while True:
slow = nums[slow] # One step
fast = nums[nums[fast]] # Two steps
if slow == fast:
break
# Phase 2: Find cycle entry (the duplicate value)
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
This runs in O(n) time with O(1) space—impossible with naive approaches that don’t modify the array.
Cycle Detection in Functional Sequences
Any function that maps a finite set to itself eventually cycles. Floyd’s algorithm detects this:
def find_cycle_in_sequence(f, x0):
"""
Given function f and starting value x0,
find cycle length and start position in sequence:
x0, f(x0), f(f(x0)), ...
Returns (mu, lambda) where mu is steps to cycle start,
lambda is cycle length.
"""
# Phase 1: Find meeting point
slow = f(x0)
fast = f(f(x0))
while slow != fast:
slow = f(slow)
fast = f(f(fast))
# Phase 2: Find cycle start position (mu)
mu = 0
slow = x0
while slow != fast:
slow = f(slow)
fast = f(fast)
mu += 1
# Phase 3: Find cycle length (lambda)
lam = 1
fast = f(slow)
while slow != fast:
fast = f(fast)
lam += 1
return mu, lam
This applies to random number generator analysis, cryptographic hash collision detection, and any iterative process over a finite domain.
Complexity Analysis and Edge Cases
Time Complexity: O(n). The slow pointer visits each node at most twice (once before meeting, once finding entry). The fast pointer moves at most 2n steps total.
Space Complexity: O(1). Only two pointer variables regardless of input size.
Edge Cases to Handle:
- Empty list (head is None)
- Single node without cycle
- Single node pointing to itself
- Cycle starting at the head
- Cycle starting at the last node
The implementation above handles all these cases through the initial null checks and the loop conditions.
Alternative: Brent’s Algorithm
Richard Brent developed a variant that’s theoretically faster in practice. Instead of moving both pointers continuously, it moves only the fast pointer while periodically teleporting the slow pointer forward. This reduces the number of equality comparisons. However, Floyd’s algorithm remains more widely used due to its simplicity and the negligible real-world performance difference for most applications.
Floyd’s algorithm is one of those rare solutions that’s both mathematically elegant and practically useful. The constant space requirement makes it applicable in constrained environments, and the technique of treating implicit structures as graphs opens up non-obvious problem solutions. Master this pattern—it appears in interviews frequently and solves real problems efficiently.