Floyd Cycle Detection

Floyd Cycle Detection

Floyd cycle detection, also known as the tortoise and hare, decides whether a sequence eventually repeats and where the loop begins, using only two pointers and constant memory. It applies to linked lists and to functions iterated on a value.

Phase one detect

Advance a slow pointer one step and a fast pointer two steps at a time. If there is a cycle the fast pointer wraps around and the two eventually land on the same node. If the fast pointer reaches the end, there is no cycle.

Phase two locate

Once they meet, reset one pointer to the start and move both one step at a time. The node where they meet again is the entrance of the loop. This works because of a neat distance relationship between the meeting point and the loop start.

Why it beats hashing

A hash set of visited nodes also detects cycles but uses linear extra memory. Floyd method needs only two pointers, making it ideal when space is tight.

Key idea

Two pointers at different speeds detect a loop, then a reset and equal pace find where it starts.