Floyd's Cycle Detection Algorithm
Click "Start" or "Step" to begin the algorithm
Medium
Find the duplicate in array without modifying it.
Solve on LeetCode →If there's a cycle, the fast pointer will eventually "lap" the slow pointer, like runners on a circular track. If there's no cycle, the fast pointer will reach the end.
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next; // Move 1 step
fast = fast.next.next; // Move 2 steps
if (slow === fast) {
return true; // Cycle detected!
}
}
return false; // No cycle
}After detecting a cycle, reset one pointer to head. Move both at same speed - they meet at the cycle start!
function detectCycle(head) {
let slow = head, fast = head;
// Phase 1: Detect cycle
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) break;
}
if (!fast || !fast.next) return null;
// Phase 2: Find start
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // Cycle start!
}