Floyd's cycle detection: slow, fast, then reset
What interviewers are testing
Floyd's tortoise-and-hare is a favorite because the code is five lines but the proof is not. Interviewers watch whether you can argue that the pointers must meet, and whether you realize the meeting point is not necessarily the cycle entrance. The reset trick and the distance argument behind it separate candidates who memorized the algorithm from those who can derive it. It also tests space-awareness: a visited set works, but interviewers want to hear why O(1) space matters here.
Mental model
A slow pointer moves one node per step and a fast pointer moves two. If the list ends, there is no cycle. If there is a cycle, both pointers eventually enter it, and once they are inside, the forward distance from fast to slow shrinks by exactly one node per step, so it must reach zero. That meeting proves a cycle; resetting slow to the head and then advancing both one step at a time makes them meet again, this time at the cycle entrance.
Step-by-step solution
Step 1 of 5
The loop that never ends
Traversal code usually assumes the list ends: follow next until null. A cycle breaks that assumption, and the traversal spins forever without any error - the classic production hang in parsers, walkers, and garbage collectors. Before doing expensive work like reversing a list or serializing it, you need to know whether the structure terminates. The brute-force detector keeps a set of every visited node and flags the first repeated reference; it works, but it stores one entry per node, so it costs O(n) extra memory and cannot run where memory is tight. The animation shows a walk over 3 -> 2 -> 0 -> -4 -> 5 -> back to 0: after five steps the walk revisits node 0 and would keep repeating the same three nodes forever. That picture is the motivation for a detector that uses constant memory.
Animation — The loop that never ends
Linked list nodes (heap)
heapThe list is 3 -> 2 -> 0 -> -4 -> 5, and node 5 points back to node 0: there is no null tail.
Edge cases & traps
- Cycle at the head: the reset phase still converges at the head, but code that assumes the entrance differs from the meeting point breaks - trace [1, 2] with 2 pointing back to 1 to verify.
- A single node pointing to itself: fast must check fast and fast.next before the double step, or the second hop dereferences null.
- Even-length acyclic lists: fast.next is null while fast is not, so the loop must test both conditions rather than only fast.
- Stopping at the first meeting: the meeting node is the entrance when the head-to-entrance distance is congruent to 0 modulo the cycle length (a ≡ 0 (mod L)), not only when a = 0 — always run the reset phase before claiming the entrance.
- Mutating nodes to mark visited (for example stealing a spare flag) corrupts the list for concurrent readers; when no allocation is allowed, Floyd is the safe alternative.