Pattern Guide
Cycle Detection
"Floyd's tortoise and hare. O(n) time, O(1) space. Detects AND finds the cycle."
Cycle detection in linked lists and function sequences uses Floyd's algorithm (tortoise and hare) — two pointers at different speeds meet inside the cycle, then reset one to find the cycle start. Applies to: linked list cycles, find duplicate (array as linked list), Floyd cycle in sequences.
14 min readlinked list problems →
Problems you can solve with this pattern
5 problems · click any to start solving
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"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"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).