How do you detect a cycle in a linked list in O(1) space, and why does it work?

A strong answer

The simple solution stores every visited node in a hash set and stops at the first repeat: O(n) time, O(n) space. Floyd's cycle-finding algorithm gets O(1) space with two pointers. slow moves one node per step and fast moves two. If the list ends, fast reaches null and there is no cycle. If there is a cycle, both pointers eventually enter it, and from then on fast gains exactly one node on slow per step. The gap between them shrinks by one every step, so it reaches zero: they meet, within one lap of slow entering the cycle. Total time is O(n).

To find where the cycle starts, reset one pointer to the head and leave the other at the meeting point, then move both one step at a time; they meet at the cycle's first node. Proof: let a be the distance from the head to the cycle start, b the distance from the start to the meeting point, and L the cycle length. At the meeting, slow walked a + b and fast walked 2(a + b), so the extra a + b is a whole number of laps: a + b = kL. Hence a = kL − b, so walking a steps from the meeting point lands on the cycle start, exactly as walking a steps from the head does.

The cycle's length is found by keeping one pointer fixed after the meeting and counting steps until the other returns.

What the interviewer is listening for

• The O(n)-space baseline and why the two-pointer version is better.
• A real argument for why the pointers meet, not just "fast catches up".
• The second phase and its derivation.
• Comparing nodes by identity, not by value.

Common mistakes

• Checking fast.next.next without first checking fast.next, which crashes on lists of odd length.
• Comparing values instead of node identity, which reports false cycles when values repeat.
• Claiming any speed works: with a speed difference of more than one, the pointers can step past each other repeatedly, so the meeting argument no longer holds.