What is Floyd’s Cycle Detection Algorithm?
Learn how Floyd’s tortoise-and-hare algorithm detects a cycle and finds its start node, with code and interview tips.
Expected Interview Answer
Floyd’s cycle detection algorithm, also called the tortoise-and-hare algorithm, finds whether a linked structure contains a cycle and, with a second phase, locates the exact node where the cycle begins, using two pointers moving at speeds of one and two nodes per step, in O(n) time and O(1) space.
Phase one moves a slow pointer one step and a fast pointer two steps per iteration; if they ever meet, a cycle exists. Phase two exploits a mathematical property: resetting one pointer to the head and advancing both remaining pointers one step at a time causes them to meet exactly at the cycle’s entry node, because the distance from the head to the cycle start equals the distance from the meeting point to the cycle start, measured around the loop. This two-phase structure is what distinguishes Floyd’s algorithm from a simple cycle check — it fully localizes the cycle, not just detects it. It is a classic building block for problems like finding a duplicate number in an array framed as a linked-list cycle.
- Detects a cycle in O(n) time, O(1) space
- Second phase locates the cycle’s start node exactly
- No modification of the underlying structure required
- Generalizes to array-based cycle problems, not just linked lists
AI Mentor Explanation
A groundskeeper first confirms two joggers on the boundary rope meet at all, using a normal-pace jogger and a double-pace jogger starting together. Once they meet somewhere on the loop, phase two resets the double-pace jogger to the starting gate and has both joggers now move at the same normal pace. They will arrive at the exact same spot on the rope at the same time, and that spot is precisely where the loop rejoins the straight approach path, thanks to the equal distances created by the first phase’s geometry.
Step-by-Step Explanation
Step 1
Phase one: detect
Move slow one step and fast two steps per iteration until they meet or fast reaches null.
Step 2
Confirm a cycle exists
A meeting point confirms a cycle; reaching null confirms none.
Step 3
Phase two: locate the start
Reset one pointer to head, keep the other at the meeting point, then advance both one step at a time.
Step 4
Find the entry node
The two pointers meet exactly at the node where the cycle begins.
What Interviewer Expects
- Describe both phases, not just cycle detection
- Explain why resetting one pointer to head locates the cycle start (distance equality)
- State the overall O(n) time and O(1) space complexity
- Connect the algorithm to related problems like finding a duplicate number via cycle detection
Common Mistakes
- Stopping after phase one and being unable to locate the cycle start when asked
- Resetting the wrong pointer to head in phase two
- Advancing both pointers at different speeds during phase two instead of the same speed
- Not being able to justify why the meeting point math works
Best Answer (HR Friendly)
“Floyd’s algorithm has two phases: first, two pointers moving at different speeds meet if there’s a loop; second, I reset one pointer to the start and move both at the same speed, and where they meet again is exactly the start of the loop. It’s an elegant way to both detect and pinpoint a cycle using no extra memory.”
Code Example
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def detect_cycle_start(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
pointer = head
while pointer is not slow:
pointer = pointer.next
slow = slow.next
return pointer
return NoneFollow-up Questions
- Why does resetting one pointer to head correctly find the cycle’s start node?
- How would you compute the length of the cycle once found?
- How does this algorithm relate to finding a duplicate number in an array using cycle detection?
- What happens if the list is empty or has a single self-referencing node?
MCQ Practice
1. In Floyd’s algorithm phase two, what is reset to the head?
One of the pointers that met in phase one is reset to head, and both then move one step at a time.
2. What speed do both pointers move at during phase two?
Phase two requires both pointers to advance one step at a time so they meet exactly at the cycle entry.
3. What is the overall time complexity of Floyd’s full two-phase algorithm?
Both phases each take at most O(n) steps, keeping the overall complexity linear.
Flash Cards
What are the two phases of Floyd’s cycle detection algorithm? — Phase one detects whether a cycle exists; phase two locates the exact node where it begins.
What is another common name for this algorithm? — The tortoise-and-hare algorithm.
What is the space complexity of the full algorithm? — O(1), using only a constant number of pointers.
What mathematical property makes phase two work? — The distance from head to cycle start equals the distance from the meeting point to the cycle start around the loop.