The Fast and Slow Pointers Pattern

The pattern is two pointers that travel through the same structure at different rates. The slow pointer moves one step at a time and the fast pointer moves two. Every problem that asks something about the structure of a list or a sequence becomes tractable, because the difference between the two positions is a function of the distance travelled.

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


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


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

The output is True. The third node points back to the first, so the list loops and the two pointers eventually land on the same node.

The three classics are cycle detection, where the pointers eventually meet because the fast one laps the slow one; finding the middle, where the fast one reaches the end at exactly twice the distance the slow one has covered; and finding the cycle entry point, which follows from cycle detection with a second phase.

The mechanism is the growing gap. After k steps the fast pointer has travelled two k nodes and the slow one k, so the gap is k. If the structure is finite and looping, that gap eventually becomes a whole number of laps and the pointers coincide. If the structure is a finite list, the fast pointer simply runs out first.

The trade-off to name is space against passes. The pattern uses a constant amount of extra memory and often a single pass, whereas the straightforward alternatives either use a hash set with linear space or make two passes over the data. What it costs is readability: every loop condition has to check the fast pointer and its successor, because advancing two steps requires two nodes to exist, and that detail is where most bugs in this family live.

Run the standard cycle detection first. Once the two pointers meet, put the slow pointer back at the head and move both one step at a time. The node where they meet the second time is the entry point of the cycle.

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


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


print(cycle_entry(None))
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = head.next
print(cycle_entry(head).value)

The outputs are None and 2. The first list has no cycle at all, and in the second the cycle starts at the node with value two, because the third node points back to it.

The mechanism is a distance argument. Let the distance from the head to the cycle entry be a and the length of the cycle be c. When the pointers first meet, the fast pointer has covered a plus some multiple of c and the slow pointer has covered a plus some smaller multiple of c, and the difference between their travelled distances is a whole number of laps. Resetting the slow pointer to the head and advancing both by one means the slow pointer has covered a and the fast pointer has covered a plus a multiple of c, so they land on the same node only when that node is the entry point.

The trade-off to name is that this needs two phases and a node identity comparison, so it is more involved than simply detecting that a cycle exists. The set-based alternative finds the entry in one pass and is much easier to write, at the cost of linear space. In production you would also want to decide what to do once you have the entry node, because merely reporting it leaves the cycle in place and any traversal of the list will still loop forever.