Floyd's Cycle Detection: The Tortoise and the Hare & Cycle Entry
Master cycle detection in node graphs. Prove Floyd's Tortoise and Hare algorithm, locate cycle existence, and mathematically derive the cycle entry node.
By the end, you’ll be able to…
- Detect cycles in a linked list in O(N) time and O(1) auxiliary space using Floyd's Tortoise and Hare algorithm.
- Derive the mathematical proof for finding the exact starting node of a cycle.
- Apply cycle detection to solve the 'Find the Duplicate Number' array problem in O(N) time without extra memory.
01The Problem of Cycle Detection
If a linked list contains a cycle (a node whose next pointer points back to a previously visited node), a standard while (curr != null) traversal will enter an infinite loop, freezing the thread and exhausting CPU.
A naive solution stores visited node references in a HashSet. While this detects cycles in O(N) time, it consumes O(N) auxiliary space. For a list of 10 million nodes, this requires hundreds of megabytes of hash map overhead. Floyd's Cycle-Finding Algorithm (Tortoise and Hare) detects cycles in O(N) time using strictly O(1) space.
02Mathematical Proof of Cycle Collision
Why is a collision mathematically guaranteed if a cycle exists? Consider the relative speed between the two pointers: on every step, fast moves 2 steps while slow moves 1 step. From the frame of reference of slow, fast closes the gap by exactly 1 node per iteration: distance = distance - 1.
Because the distance decreases by 1 on each step, fast cannot 'jump over' slow! The distance will inevitably decrease to 0, guaranteeing a collision within at most C iterations (where C is the cycle length).
+---------------------------------------------------+| Floyd's Cycle Geometry |+---------------------------------------------------+| Head -------[ L ]-------> Entry Node || / \ || [ d ] [ C - d ] || \ / || Collision Point |+---------------------------------------------------+03Locating the Exact Cycle Entry Node
How do we find the exact node where the cycle begins (Entry Node)? Let L be the distance from Head to Entry. Let C be the cycle circumference, and d be the distance from Entry to the collision point.
When they collide: Distance traveled by slow = L + d Distance traveled by fast = L + d + nC (for some integer n) Since fast travels twice as fast as slow: 2(L + d) = L + d + nC => L + d = nC => L = nC - d = (n - 1)C + (C - d). This mathematical identity reveals an incredible symmetry: the distance from Head to Entry (L) equals the distance from the collision point to Entry (C - d)!
Therefore: Reset slow to Head. Keep fast at the collision point. Advance BOTH pointers at 1 step per iteration. The node where they collide is GUARANTEED to be the Cycle Entry Node!
04Why This Matters in Production
Cycle detection is a critical safety mechanism in distributed dependency graphs (such as detecting circular dependency deadlocks in Spring Beans or Maven build POMs) and network routing protocols (like preventing routing loops in Border Gateway Protocol / BGP).
Floyd's algorithm can also be applied to arrays where numbers map to indices (nums[i] -> next index), allowing problems like 'Find the Duplicate Number' to be solved in O(N) time with zero extra memory without modifying the read-only array.
The ideas worth keeping.
- Floyd's Tortoise and Hare algorithm detects cycles in O(N) time and O(1) space.
- The relative speed of 1 guarantees a collision within the cycle without skipping.
- Advancing from head and collision point at speed 1 pinpoints the exact cycle entry node.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Exercise 1: Find the Duplicate Number via Floyd's Algorithm
Given an array of N + 1 integers where each integer is between 1 and N, use Floyd's Tortoise and Hare algorithm to find the duplicate number in O(N) time and O(1) space.
Explore a worked solution
public int findDuplicate(int[] nums) { int slow = nums[0], fast = nums[0]; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); slow = nums[0]; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow;}Treating nums[i] as a pointer maps duplicate numbers to converging cycle entry points in O(1) space.
Exercise 2: Calculate Cycle Length
Once a collision point is detected in Floyd's algorithm, explain how to determine the exact number of nodes in the cycle in O(C) time.
Explore a worked solution
Hold fast fixed at the collision node. Advance slow by 1 step and maintain a counter (count = 1) until slow equals fast again. count is the exact cycle length C.Traversing from the collision point around the cycle back to itself counts the exact circumference.
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Exercise 1: Find the Duplicate Number via Floyd's Algorithm
Given an array of N + 1 integers where each integer is between 1 and N, use Floyd's Tortoise and Hare algorithm to find the duplicate number in O(N) time and O(1) space.
Build successful. (Java 15) [Process exited normally]
Keep exploring.
The official references behind this lesson, when you want a second angle or the full details.
One lesson closer.
Reading is a start. Trying it yourself makes the connection.