Floyd's cycle detection
mediumThe fast pointer gains one position per step on the slow one, so they must meet. Then restarting one at the head finds the loop entry - and the algebra behind that is worth seeing once.
O(n)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How floyd's cycle detection works
March two pointers down the list: slow moves one node per step, fast moves two. If the list terminates, fast falls off the end and there is no cycle. If there is a loop, both pointers eventually enter it - and inside the loop, fast gains exactly one position on slow per step, so the gap shrinks to zero. They must meet; they cannot jump past each other.
The surprise is phase 2. Send one pointer back to the head, leave the other at the meeting point, and advance both one step at a time - they collide precisely where the loop begins. The algebra: with tail length T, loop length L and meeting offset K, slow walked T + K while fast walked twice that, so T + K is a whole number of loops and T = mL - K.
A hash set of visited nodes finds the same cycle in O(n) memory. Floyd's does it with two pointers and nothing else, which is why it is the expected answer the moment an interviewer adds the constant-space constraint - and why it resurfaces in problems like finding a duplicate number.
Step by step
- Build 8 nodes where node 7 points back at node 3 - a tail of 3 feeding a loop of 5. Both pointers start at node 0.
- After four rounds slow stands at node 4 while fast, having wrapped past node 7, stands at node 3.
- Round five: slow steps to node 5; fast hops through 4 to 5. They collide - a cycle definitely exists.
- Phase 2: send slow back to node 0, leave fast at node 5, and advance both one step per round.
- slow walks 1, 2, 3 while fast walks 6, 7, 3. They meet at node 3 - the loop entry.
- Check the numbers: tail 3 plus meeting offset 2 equals one full loop of 5 - the identity T = mL - K, working.
Complexity
| Worst case time | O(n) |
|---|---|
| Space | O(1) |
Reference implementation
Python
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None # fast fell off the end
if not fast or not fast.next:
return None
slow = head # phase 2
while slow is not fast:
slow = slow.next
fast = fast.next
return slow # entry point of the loopJavaScript
function detectCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) break;
}
if (!fast || !fast.next) return null;
slow = head; // phase 2
while (slow !== fast) { slow = slow.next; fast = fast.next; }
return slow; // entry point
}Worth noticing
Why they must meet
Once both pointers are inside the loop, the fast one gains exactly one position per step on the slow one. The gap shrinks by 1 every step, so it reaches zero - they cannot jump past each other.
Why restarting at the head finds the entry
Let the tail be length T and the meeting point be K steps into the loop of length L. Slow travelled T+K, fast travelled 2(T+K), and the difference is a whole number of loops: T+K = mL. So T = mL − K - which is exactly the distance from the meeting point back round to the entry. Two pointers moving at the same speed from head and from the meeting point therefore collide at the entry.
O(1) memory is the point
A hash set of visited nodes also finds the cycle, in O(n) memory. Floyd's does it with two pointers - which is why it is the answer when the interviewer adds 'now do it in constant space'.
Common pitfalls
- Guarding only fast: the loop needs fast and fast.next both non-null, or fast.next.next dereferences null on a list that ends.
- Comparing values instead of node identities: duplicate values produce false meetings. Test slow is fast, not slow.value equals fast.value.
- Testing equality before stepping: both pointers start at the head, so they are equal before either moves - the check belongs after the advance.
- Forgetting that phase 2 changes speed: both pointers now move one step. Leaving fast at double speed overshoots the entry.
Where it is used
- Detecting cycles in linked lists - LeetCode 141 and 142 verbatim.
- Finding the duplicate number in an array read as a linked list, LeetCode 287.
- Cycle detection in iterated functions - the happy number problem is the classic case.
- Any environment too memory-tight for a visited set, such as embedded code walking untrusted structures.
Frequently asked questions
What is the time and space complexity of Floyd's cycle detection?
O(n) time and O(1) space. Slow travels at most the tail plus one lap before the meeting, fast at most twice that, and phase 2 adds at most another tail's length. Memory is exactly two pointers, no matter how long the list is.
Why do the slow and fast pointers always meet?
Once both are inside the loop, fast gains exactly one position on slow each step. The gap shrinks by one per step, so it must reach zero - and because the gain is exactly one, fast can never skip over slow without landing on it.
How does restarting at the head find where the cycle starts?
At the meeting point slow has walked T + K steps - tail plus offset into the loop - and fast twice that, so T + K is a multiple of the loop length. That makes T exactly the distance from the meeting point forward to the entry, so two same-speed pointers starting from the head and the meeting point collide there.
Why not just use a hash set of visited nodes?
A set works and is easier to write: walk the list and return the first node seen twice. But it costs O(n) extra memory. Floyd's trades that for two pointers, which matters on constrained systems - and is usually the follow-up the interviewer is fishing for.