Fast & Slow Pointers (Floyd’s Tortoise and Hare Algorithm)

Every developer meets the infinite loop the hard way. Mine was a linked structure that, thanks to one careless pointer assignment, quietly looped back on itself: the traversal never ended, the process just sat there pinning a core, and the logs said nothing. The clean way to catch that is almost embarrassingly simple, and it is one of the prettiest ideas in the whole catalog. Send two walkers through the structure at different speeds and watch what happens.

Why the hare always laps the tortoise

Both pointers start at the head. The slow one steps one node at a time; the fast one steps two. If the list simply ends, the fast pointer runs off the end and you are done: no cycle. But if there is a cycle, the fast pointer enters the loop and starts circling. The slow pointer eventually enters too, and now you have two runners on a circular track moving at different speeds.

Here is the part worth holding onto. Once both are inside the loop, the fast pointer closes the gap on the slow one by exactly one node every step. A gap that shrinks by one each step cannot leap over zero, so it has to land on it. They meet. No visited-set, no extra memory, just two pointers and a guarantee from arithmetic. The toy version, on an actual linked list:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

That is O(n) time and O(1) space, against the O(n) space a hashset of visited nodes would burn.

A linked list shaped like the letter rho: a straight tail feeding into a loop. A slow pointer moves one node per step and a fast pointer two; both start at the head, and if the list loops the fast pointer laps the slow one, the gap shrinking by one each step until they meet on a node inside the loop, all in constant space.

In the wild: catching a redirect loop

The linked list is where you learn it, but the pattern is not really about nodes. A web crawler following 301 and 302 responses can get trapped: page A redirects to B, B back to A, forever. You could remember every URL you have seen, but on a long chain that is a growing set for what is really just cycle detection. Treat "the URL this one redirects to" as the next pointer, and the redirect chain is a linked list nobody ever built in memory:

def has_redirect_loop(start, resolve):
    # resolve(url) -> the URL it redirects to, or None if it is a final page
    slow = fast = start
    while True:
        slow = resolve(slow)
        if slow is None:
            return False                # the chain ended, no loop
        fast = resolve(fast)
        if fast is None:
            return False
        fast = resolve(fast)
        if fast is None:
            return False
        if slow == fast:
            return True                 # tortoise met hare, the redirects loop

Nothing here is a linked-list node, yet it is exactly the tortoise and hare, because resolve is a deterministic "next": the sequence of URLs either terminates at a real page or repeats, and two pointers at different speeds catch the repeat in constant space. That is what makes it the same class of problem. Any deterministic step function, redirects, a state machine, the digit-square-sum of Happy Numbers, spins out a sequence that fast and slow can probe for a cycle without ever storing its history.

The follow-up: where does the loop start?

Detecting a cycle is the easy half. The classic interview follow-up, the one that separates "I memorized this" from "I understand this," is finding the node where the cycle begins. There is a small piece of magic: after the two pointers meet, send one of them back to the head and advance both one step at a time. The node where they meet again is the start of the cycle.

def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                  # a meeting point inside the loop
            slow = head
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow
    return None

The reason is a short distance argument: the walk from the head to the loop's entrance is the same length as the walk from the meeting point to that entrance. You do not need to re-derive it live, but knowing the second loop is not arbitrary is what lets you reproduce it under pressure instead of guessing.

The trigger

A linked structure, or any sequence you can only step through, and a question about a cycle, a midpoint, or a meeting point. When the interviewer adds "in constant space," it is practically a neon sign. The phrase "without extra memory" on a linked-list problem almost always means fast and slow.

Where it shows up

  • Cycle detection, and the sharper version, finding the cycle's entry node.
  • Finding the middle in one pass: when the fast pointer reaches the end, the slow one is halfway, which is how you split a list for a merge sort without counting its length first.
  • Palindrome linked list: find the middle, reverse the second half in place, walk the halves toward each other.
  • Happy number and its relatives, where you iterate a function until a value repeats and the repetition is a cycle in an invisible list.

Where it bites

The whole thing rests on fast and fast.next both existing before you evaluate fast.next.next. Get that guard wrong and you dereference null on the very first empty or single-node list. Order matters too: test for the meeting after you move the pointers. Check slow is fast before the first step and it is always true, reporting a cycle in a straight line.

When to reach for something else

Fast and slow is a scalpel, not a universal tool, and its constant-space elegance stops paying the moment you need more than a yes or no. To know the cycle's length, or to collect every node on it, a hashset that records what you have visited is simpler and just as fast. If the "next" step is not a single deterministic successor, if a node can branch to several, then there is no tortoise and hare to run and you are really doing a graph search. And on a structure short enough that memory is a non-issue, the plain visited-set is clearer than the two-speed dance. Save the trick for when constant space genuinely matters, not as a reflex.

Its neighbors

It is really Two Pointers with a twist: instead of starting at opposite ends and converging, both start together and separate by moving at different rates. It pairs constantly with Linked List Techniques (dummy nodes, in-place reversal) in problems that first locate a position and then rewire around it. And the "iterate until it repeats" framing quietly links it to cycle-finding in any process with finitely many states.

References