Why This Matters
Floyd's cycle detection is the cleanest example of a two-pointer speed trick. It detects cycles without a visited set, which matters when memory is tight or the structure only exposes a next operation.
It is common in linked-list problems, functional graphs, repeated-state processes, and bug detection in pointer structures.
Core Idea
Move one pointer one step at a time and another pointer two steps at a time.
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return cycle exists
return no cycle
If a cycle exists, the fast pointer eventually laps the slow pointer inside the cycle.
Non-Example or Failure Mode
This does not find arbitrary cycles in a general graph. It works for structures where each node has at most one next pointer. For general graph cycle detection, use DFS or topological methods.
Worked Example
In A -> B -> C -> D -> B, slow and fast eventually both enter the cycle B, C, D. Because fast gains one node per iteration relative to slow, their distance modulo the cycle length eventually becomes zero.
Common Mistakes
| Mistake | Correction |
|---|---|
| Using it on general adjacency-list graphs. | Use DFS or graph-specific cycle detection. |
Moving fast.next.next without checking null. | Guard both fast and fast.next. |
| Thinking the first meeting point is the cycle start. | It proves a cycle; a second phase finds the entry. |
Diagnostic Questions
| Question type | Question | Answer signal |
|---|---|---|
| Definition | What do the two pointers do? | Slow moves one step; fast moves two. |
| Example / non-example | Does it work for a binary tree with child pointers? | Not directly; the next relation is not single-valued. |
| Computation | What extra memory is used? | O(1). |
| Transfer | Why is this useful in repeated-state simulations? | A deterministic next-state function creates a functional graph. |
Exercises
Beginner:
- Trace slow and fast pointers on a 5-node cycle.
- Explain why null means no linked-list cycle.
- Identify the missing null check in a buggy implementation.
Intermediate:
- Implement cycle detection for a singly linked list.
- Add the second phase that returns the cycle entry.
Challenge:
- Apply Floyd cycle detection to repeated values of
x = f(x)and detect periodic behavior.
Diagram Recommendation
Type: circular linked-list trace.
Caption: "Fast pointer gains one position per iteration inside the cycle."
Purpose: Explain why the pointers must meet.
Next Topics
References
- Floyd, R. W. cycle-finding method, commonly known as tortoise and hare.
- Sedgewick and Wayne. Algorithms (4th ed., 2011). Linked structures and cycle detection context.