Measure the length of a linked list's cycle

Question

A traversal has confirmed that a linked list contains a cycle. The next diagnostic question from your monitoring system is: how big is the loop?

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

Return the number of nodes in the cycle in $O(n)$ time and $O(1)$ space. Return $0$ if there is no cycle.

Accepted Answer

First run Floyd's two pointers until slow and fast meet, which guarantees the meeting node is somewhere on the cycle. Then freeze that node and walk a single pointer around until it comes back to the meeting node, counting steps. Since you started and ended on the same cycle, the count is the cycle length. Trace on 1 - 2 - 3 - 4 - 5 - (back to 3). The pointers meet on a cycle node; suppose they meet at node 3. Walking from 3.next: node 4 (length 1), node 5 (length 2), then 5.next is 3, which is the start, so we stop with length 3. The loop 3 - 4 - 5 - 3 indeed has 3 nodes. The identity check …

Measure the length of a linked list's cycle

Your answer

More Coding questions