Detect a cycle in a linked list

Question

A misbehaving feed handler built a linked list of messages, and a bug may have spliced a node's next pointer back to an earlier node, so traversal never terminates.

1 -> 2 -> 3 -> 4
          ^    |
          +----+        # 4 points back to 3: cycle

Detect whether the list contains a cycle in $O(n)$ time and $O(1)$ space. A hash set of visited nodes works but costs $O(n)$ memory, the interviewer wants Floyd's algorithm.

Accepted Answer

Run two pointers: slow advances one node per step, fast advances two. If there is no cycle, fast reaches the end. If there is a cycle, both pointers eventually enter it, and inside the cycle fast gains one position on slow per step, so the gap shrinks by exactly 1 each step and they must meet before slow completes one lap. Note the identity check is, we're asking whether they are the same node object, not nodes with equal values. Time O(n), space O(1). Finding the cycle's entry point is the standard follow-up. After the meeting, reset one pointer to head and advance both one step at a time; t…

Detect a cycle in a linked list

Your answer

More Coding questions