1. One-Liner
Floyd’s algorithm moves a slow pointer one step and a fast pointer two steps; they meet iff a cycle exists.
2. The Problem It Solves
Detect cycles in linked structures without extra memory—important for memory leak checks, list integrity, and interview classics.
3. The Core Idea
If there is a cycle, the fast runner eventually enters the loop and catches the slow one inside; if null-terminated, fast reaches end first.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | slow=fast=head |
| 2 | While fast and fast.next: advance slow by 1, fast by 2 |
| 3 | If slow==fast → cycle |
| 4 | Else end → no cycle |
5. Dry Run Example
List 1→2→3→2 (back): slow and fast meet at some node inside the loop after finite steps.
6. Key Properties
| Property | Detail |
|---|---|
| Space | O(1) pointers only |
| Time | O(n) meet time |
| Phase | Detection only; entry node needs extra step |
7. Where It Is Used
| Domain / System | Use |
|---|---|
| Runtimes | Cycle in linked structures |
| Databases | Row chains |
| Security | Pointer validation |
8. Interview Tips
Follow-up: start of cycle using meeting point + second pointer from head. Know why fast=3x also works but different analysis.
9. Comparison with Other Algorithms
| Technique | Notes |
|---|---|
| Hash set of nodes | O(n) memory |
| Brent’s algorithm | Alternative stepping |
| DFS on graph | Different model |
10. Complexity
| -- | -- |
|---|---|
| Time | O(n) |
| Space | O(1) |
Implementation Example (PYTHON)
class ListNode:
def __init__(self, x): self.val = x; self.next = None
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False