Fast and Slow Pointers

The fast and slow pointers pattern (often called "Floyd's tortoise and hare") uses two pointers that traverse a sequence at different speeds — typically one step at a time for the "slow" pointer and two steps at a time for the "fast" pointer. This simple idea unlocks elegant, constant-space solutions to a surprising number of problems involving linked lists, arrays treated as implicit graphs, and even numeric sequences.

Why not just use a hash set?

The naive way to detect a cycle in a linked list is to walk the list while storing every node you visit in a hash set, checking before each step whether the next node has already been seen. That works, but it costs O(n) extra space. The fast and slow pointer technique achieves the same result — and can also locate the start of the cycle — using only two pointer variables, for O(1) space. When you see a problem where you need to detect a repeating state or find a "meeting point" in a sequence, ask whether it can be modeled as pointer movement through a chain of nodes.

The core template

slow = head
fast = head

while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        # cycle detected
        break
else:
    # fast (or fast.next) hit None: no cycle
    return False

If the pointers meet, a cycle exists. To find where the cycle begins, reset one pointer to the head and advance both pointers one step at a time from there — they are mathematically guaranteed to meet exactly at the start of the cycle. This works because the distance from the head to the cycle start equals the distance from the meeting point to the cycle start, when both are measured going forward around the cycle.

For midpoint problems, the same two pointers are used without a meeting-point check: when fast reaches the end, slow sits at the midpoint, because it has covered exactly half the distance.