Floyd's Cycle Detection: Tortoise and Hare

Detecting whether a cycle exists

Set a slow pointer and a fast pointer to the list head. Advance slow by one link and fast by two. If fast reaches None (or its next link is None), the list ends and has no cycle. If there is a cycle, fast eventually meets slow inside it: each iteration fast gains one node relative to slow.

def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Comparing node identity matters. Two different nodes may contain the same value, but a cycle is about revisiting the same node.

Find the cycle's entry node

After the pointers meet, reset one pointer to the head. Move both one step at a time. They meet again at the first node of the cycle. To see why, let μ be the number of steps from the head to the cycle entry, and λ the cycle length. At the first meeting, fast has traveled twice as far as slow; their distance difference is a whole number of cycle lengths. This makes the remaining distance from the meeting point back to the entry equal, modulo λ, to the head's distance μ.

def cycle_entry(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            from_head = head
            while from_head is not slow:
                from_head = from_head.next
                slow = slow.next
            return slow
    return None

Complexity and related uses

The algorithm runs in O(n) time and O(1) extra space. A hash set of visited nodes is simpler to explain and can identify a repeat in one pass, but uses O(n) memory. The two-speed pointer idea also finds the middle of a list (fast moves twice as quickly) and appears in cycle problems over deterministic state transitions.

• Check both fast and fast.next before advancing two steps.
• Use identity comparisons, not value equality.
• Test an empty list, one node without a cycle, a self-loop, and a cycle that begins at the head.