Pattern Reference
Cycle Detection
"Floyd's tortoise and hare, Brent's algorithm. Cycle in LL, arrays, functional graphs."
Loading...
Deep Dive Tutorial
Floyd's cycle detection algorithm uses two pointers: slow (moves 1 step) and fast (moves 2 steps). If there's a cycle, they must meet inside it. Once they meet: reset slow to start, keep fast at meeting point, advance both 1 step — they'll meet again at the cycle's entry point. O(n) time, O(1) space.
Floyd's Algorithm — Template
Floyd's tortoise and hare — detect cycle AND find entry point
// PHASE 1: Detect cycle — does one exist?
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true; // cycle detected
}
return false; // fast reached null = no cycle
}
// PHASE 2: Find cycle entry point
// After slow and fast meet inside cycle:
// Reset slow to head, keep fast at meeting point
// Both advance 1 step — meet again at cycle start
function detectCycle(head) {
let slow = head, fast = head;
// Phase 1: find meeting point
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) break;
}
if (!fast || !fast.next) return null; // no cycle
// Phase 2: find cycle entry
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next; // both move 1 step now
}
return slow; // cycle entry node
}
// WHY DOES PHASE 2 WORK?
// Let d = distance from head to cycle start
// Let c = cycle length, m = meeting point distance from cycle start
// When they meet: slow traveled d+m, fast traveled d+m + kc (k full cycles extra)
// fast = 2×slow → 2(d+m) = d+m+kc → d+m = kc → d = kc-m
// From meeting point, distance to cycle start = c-m (almost there)
// d = kc-m = (k-1)c + (c-m) → "distance from head" = "distance from meeting to start"Worked Problems
rotate-ccw
Floyd's algorithm applications:
- Linked list cycle detection and entry point
- Find duplicate in array (array as linked list)
- Detect cycle in any f(x) sequence (Happy Number, etc.)
- Period detection in iterated functions
Key insight: Any sequence x, f(x), f(f(x)),... over a finite set must eventually cycle. Floyd's detects this in O(n) time and O(1) space.
Phase 2 trick: Once slow and fast meet inside cycle, reset slow to start, keep fast at meeting point. Advance both at speed 1 — they meet at cycle entry. This works because d = kc - m (see template).
- Linked list cycle detection and entry point
- Find duplicate in array (array as linked list)
- Detect cycle in any f(x) sequence (Happy Number, etc.)
- Period detection in iterated functions
Key insight: Any sequence x, f(x), f(f(x)),... over a finite set must eventually cycle. Floyd's detects this in O(n) time and O(1) space.
Phase 2 trick: Once slow and fast meet inside cycle, reset slow to start, keep fast at meeting point. Advance both at speed 1 — they meet at cycle entry. This works because d = kc - m (see template).