Detecting a Linked List Cycle
A list with a cycle has no end, so any traversal that waits for NULL runs forever. Floyd's trick is to send a second pointer at double speed: if the track loops, the faster one laps the slower and they collide. It uses two pointers and no memory, which is why it beats the obvious hash-set approach.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
struct Node {
int val;
Node* next;
};
bool hasCycle(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
int main() {
Node* a = new Node(); a->val = 1;
Node* b = new Node(); b->val = 2;
Node* c = new Node(); c->val = 3;
a->next = b; b->next = c; c->next = b;
cout << hasCycle(a) << endl;
return 0;
}Builds a three-node list whose tail points back to the second node, then detects the loop with two pointers and no extra memory.
How it works, step by step
Two speeds on the same track
slow advances one node per iteration and fast advances two. On a finite list fast reaches NULL first and the loop ends. Inside a cycle neither can escape, so they keep circling.
Why they must collide
Once both pointers are inside the cycle, the gap between them changes by exactly one node per iteration, because fast gains one net position per step. A gap that shrinks by one each step must eventually reach zero — it cannot jump over, which is the reason a step of two works and larger steps need more care.
The loop condition guards two dereferences
fast->next->next reads through two pointers, so both fast and fast->next must be non-NULL before the step. Checking them in that order is what makes the condition safe, since && short-circuits.
slow needs no null check
slow is always at or behind fast, so if fast is safe to advance, slow certainly is. That asymmetry is why only fast appears in the condition.
Finding where the cycle starts
After a meeting, reset one pointer to the head and advance both one step at a time; they meet again at the cycle entrance. That follows from the distance arithmetic — the distance from the head to the entrance equals the distance from the meeting point to the entrance, modulo the cycle length.
Complexity
The slow pointer travels at most the length of the list before the two meet inside the cycle, so the work is linear; the hash-set alternative is also O(n) time but costs O(n) memory to store every visited node.
Common bugs
Checking fast->next->next in the condition
while (fast != NULL && fast->next->next != NULL) dereferences fast->next before verifying it is non-NULL. On an even-length list without a cycle this segfaults on the final iteration. The condition must be fast != NULL && fast->next != NULL, with the double step inside the body.
Comparing values instead of pointers
if (slow->val == fast->val) reports a cycle whenever two distinct nodes happen to hold the same number. Cycle detection is about identity — compare the pointers themselves.
Starting fast at head->next
Some versions initialise slow = head and fast = head->next to make the pointers distinct before the loop. That works, but it crashes on an empty list and changes where the meeting point lands, which silently breaks the follow-up code that finds the cycle entrance. Keep both at head and check after advancing.
Assuming the meeting point is the cycle start
It almost never is. The pointers meet somewhere inside the loop determined by the entry offset, not at the entrance. Stepping through and watching where the two pointers coincide relative to the loop entry makes it clear why a second phase is needed.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
How does Floyd's cycle detection work?
Two pointers traverse the list at different speeds — one node per step and two nodes per step. If the list ends, the fast pointer reaches NULL and there is no cycle. If there is a cycle, both pointers become trapped in it and the faster one closes the gap by exactly one node per iteration until they land on the same node.
Why do the slow and fast pointers always meet in a cycle?
Because once both are inside the loop, the distance from fast to slow decreases by exactly one node each iteration — fast moves two, slow moves one, netting one step of progress. A distance that decreases by one at a time must hit zero exactly; it cannot skip past, which guarantees a meeting within at most one cycle length.
Can I detect a cycle with a hash set instead?
Yes. Store every node pointer you visit and report a cycle the first time you see one twice. It is easier to reason about and also O(n) time, but it costs O(n) memory. Floyd's algorithm gets the same answer in constant space, which is why it is the standard.
How do I find the node where the cycle begins?
After the two pointers meet, move one of them back to the head and then advance both one node at a time. The node where they meet the second time is the start of the cycle. This follows from the fact that the head-to-entrance distance and the meeting-point-to-entrance distance are congruent modulo the cycle length.