Detecting a Cycle

Give two pointers the same starting node and move them at different speeds: one step at a time and two steps at a time. If the list has no cycle, the fast pointer reaches the end and the loop ends. If it does have a cycle, the fast pointer gains on the slow one and eventually they meet at the same node.

The reasoning is a chase argument. Once both pointers are inside the cycle, the fast pointer moves one node further around the loop for every single step the slow pointer takes. A gap that is a multiple of the cycle length can never be closed by a whole number of single steps, so the fast pointer must lap the slow one and catch it. Since the cycle has finite length, the catch happens after at most one lap.

The alternative is the set approach: walk the list, remember every node you have seen, and report a cycle when you meet one twice. It is simpler to write and it also gives you the entry point for free, but it costs linear space, whereas the two pointer method uses constant space.

The trade-off to name is that the fast pointer needs both a current and a next check. If you advance it by two without first confirming that its next node exists, you get an attribute error on the last node. So the loop condition has to test that the fast pointer and its successor are both present, which is why the condition looks slightly more careful than the naive version you might first write.

Move one pointer one node at a time and the other two nodes at a time, and check whether they ever become the same node.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node


def has_cycle(head):
    slow = head
    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


print(has_cycle(None))
head = Node(1)
head.next = Node(2)
head.next.next = head
print(has_cycle(head))

The outputs are False and True. The first call has no list at all. In the second, the third node points back to the first, so the list loops forever and the pointers meet.

The mechanism is the relative speed. After each iteration the fast pointer has advanced two nodes and the slow pointer one, so the gap between them grows by one node every step. Once both are inside the cycle, the fast pointer eventually lands on the same node the slow pointer is on, and the equality check fires.

The trade-off to name is the loop condition, which tests the fast pointer and its successor rather than just the fast pointer. Advancing the fast pointer by two requires its next node to exist, so on a list of odd length the fast pointer would land on the last node and then need its successor for the next jump. Writing the condition as fast is not None and fast.next is not None handles that correctly for every length. The alternative set-based version is shorter to write but uses linear space, so the two pointer method is the right answer whenever memory matters.