Fast and Slow Pointers (Cycle Detection)

Two pointers moving at different speeds

Most list problems use a single pointer that walks from the head to the end, one node at a time. The fast and slow technique uses two pointers on the same list, but moves them at different speeds: the slow one advances one node per step, and the fast one advances two. This pairing is old enough to have a nickname, the tortoise and hare, and the difference in speed is the whole trick. Because the fast pointer covers ground twice as quickly, its position relative to the slow pointer encodes something useful about the list’s shape.

We will use the same singly linked node from the linked lists lesson: a small object that holds a value and a next reference to the following node, with the last node’s next set to None.

class Node:
    def __init__(self, value):
        self.value = value   # the data
        self.next = None     # points to the next node, or None at the end

Two things make this technique worth learning. It runs in O(n) time, because each pointer walks the list at most once. And it runs in O(1) space, because it keeps only two node references no matter how long the list is. Whenever you need to learn something structural about a list — where its middle is, or whether it loops back on itself — without building an extra copy or a set of seen nodes, reach for two pointers at different speeds.

Finding the middle in one pass

Suppose you want the middle node of a list but you do not know its length yet. The obvious plan is to walk the whole list once to count the nodes, then walk again halfway. That works, but it reads the list roughly one and a half times.

Fast and slow pointers find the middle in a single pass. Start both pointers at the head. Each step, move slow forward one node and fast forward two. By the time fast runs off the end, it has travelled twice as far as slow, so slow sits at the halfway mark.

def middle_node(head):
    slow = fast = head
    # fast moves two at a time, so check both fast and fast.next exist
    while fast is not None and fast.next is not None:
        slow = slow.next          # one step
        fast = fast.next.next     # two steps
    return slow                   # slow stopped at the middle

def build_list(values):
    """Build a linked list from a Python list; return the head."""
    head = None
    for value in reversed(values):
        node = Node(value)
        node.next = head
        head = node
    return head

print(middle_node(build_list([10, 20, 30, 40, 50])).value)      # -> 30
print(middle_node(build_list([10, 20, 30, 40, 50, 60])).value)  # -> 40

On the odd-length list 10 -> 20 -> 30 -> 40 -> 50, slow lands exactly on 30, the true middle. On the even-length list 10 -> 20 -> 30 -> 40 -> 50 -> 60, there is no single middle, and this version stops on 40, the second of the two middle nodes. That choice comes straight from the loop condition; if you wanted the first middle instead, you would stop one step earlier. The point to remember is that the halving falls out for free from the two-to-one speed ratio.

Complexity. The fast pointer visits each node at most once, so this is O(n) time and O(1) space, and it reads the list only once rather than one and a half times.

Detecting a cycle (Floyd’s algorithm)

A normal list ends at None. A corrupted or deliberately circular list has a node whose next points back to an earlier node, so following next forever never reaches None — you just loop. Walking such a list with a single pointer runs forever. We need a way to notice the loop without remembering every node we have seen (which would cost O(n) extra space).

The picture of a list with a cycle looks like the Greek letter rho (ρ): a straight tail that runs into a loop.

flowchart LR
    A["1"] --> B["2"]
    B --> C["3"]
    C --> D["4"]
    D --> E["5"]
    E --> C

Here 1 -> 2 -> 3 -> 4 -> 5 looks ordinary, except that 5’s next points back to 3 instead of None, so 3 -> 4 -> 5 -> 3 -> 4 -> 5 -> ... repeats forever. Floyd’s cycle detection finds this with the tortoise and hare. Move slow by one and fast by two as before. If fast reaches None, the list ended, so there is no cycle. But if there is a cycle, fast cannot escape it, slow eventually enters it too, and the two must collide.

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:          # they landed on the same node
            return True
    return False                  # fast reached None: no cycle

def build_cycle(values, pos):
    """Build a list whose last node links back to index pos (-1 means no cycle)."""
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if pos >= 0:
        nodes[-1].next = nodes[pos]   # create the loop
    return nodes[0]

print(has_cycle(build_cycle([1, 2, 3, 4, 5], 2)))   # -> True
print(has_cycle(build_cycle([1, 2, 3, 4, 5], -1)))  # -> False

Notice the comparison is slow is fast, not slow == fast. We are asking whether the two pointers are on the same node object, not whether two nodes hold equal values, and is tests object identity exactly.

Why they must meet

It is worth seeing why a collision is guaranteed rather than lucky. Once both pointers are inside the loop, think about the gap between them, measured as the number of steps fast would take to catch up to slow going around the loop. Each round, slow advances one and fast advances two, so fast gains exactly one step on slow every round. A gap that starts at some value and shrinks by one each round must eventually hit zero — and a gap of zero means they are on the same node. Because the gap is a whole number bounded by the loop’s length, this happens within at most one full lap of slow, so the meeting is certain and quick. If instead fast moved three steps at a time, the gap would shrink by two each round and could leap straight past zero without ever landing on it, which is why the classic version uses one and two.

Complexity. slow never travels more than the length of the list plus one lap of the cycle before the meeting, so cycle detection is O(n) time and O(1) space. That constant space is the headline: a set of visited nodes would also find the cycle, but at O(n) extra memory.

Finding where the cycle starts

Detecting that a cycle exists is often not enough; you may want the exact node where the tail runs into the loop — node 3 in the picture above. There is a small, almost magical follow-up step. After slow and fast meet inside the loop, leave one pointer at the meeting point, move the other back to the head, then advance both one step at a time. They meet again precisely at the cycle’s entrance.

def cycle_start(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:                  # phase 1: find a meeting point
            walker = head                 # phase 2: one pointer back to head
            while walker is not slow:
                walker = walker.next      # both now move one step at a time
                slow = slow.next
            return walker                 # they meet at the cycle's start
    return None                           # no cycle

print(cycle_start(build_cycle([1, 2, 3, 4, 5], 2)).value)   # -> 3
print(cycle_start(build_cycle([10, 20, 30], 0)).value)      # -> 10
print(cycle_start(build_list([1, 2, 3])))                   # -> None

The intuition, kept short: call the distance from the head to the cycle’s start a, and let the meeting point sit some distance b into the loop. Because fast travelled exactly twice as far as slow when they met, a little algebra shows the remaining distance from the meeting point around to the loop’s start equals a, the very distance from the head to that same start. So a pointer released from the head and a pointer released from the meeting point, each moving one step at a time, cover equal distances and arrive at the entrance together. You do not need to reproduce the algebra in an interview; it is enough to know the reset-to-head move works and why the two remaining distances match.

Complexity. Phase one is the ordinary detection, O(n). Phase two walks at most the length of the tail, another O(n). Total time is O(n) and space stays O(1).

The same trick on numbers: happy numbers

Fast and slow pointers are not only for linked lists. The technique works on any sequence where each value determines the next, because such a sequence is a kind of invisible linked list: the “next node” is just the next number the rule produces. If that sequence ever repeats a value, it has a cycle, and Floyd’s algorithm finds it in constant space.

A classic example is the happy number rule. Take a positive integer, replace it with the sum of the squares of its digits, and repeat. If you eventually reach 1, the number is “happy”; otherwise the sequence falls into a loop that never reaches 1. For example, starting from 4 gives 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4, which is back to 4 and so loops forever. Starting from 19 gives 19 -> 82 -> 68 -> 100 -> 1, reaching 1. Detecting the loop is exactly cycle detection, with the digit-square rule playing the role of next.

def square_digits(x):
    total = 0
    while x > 0:
        x, digit = divmod(x, 10)   # peel off the last digit
        total += digit * digit
    return total

def is_happy(n):
    slow = n                        # one hop per round
    fast = square_digits(n)         # two hops per round
    while fast != 1 and slow != fast:
        slow = square_digits(slow)
        fast = square_digits(square_digits(fast))
    return fast == 1                # exited because we hit 1, not because of a loop

print(is_happy(19))   # -> True
print(is_happy(4))    # -> False
print(is_happy(7))    # -> True

The structure mirrors has_cycle exactly. The slow value moves one step of the rule per round, the fast value moves two, and either the fast value reaches 1 (the sequence’s “end,” so the number is happy) or the two values collide inside a loop (so it is not). Because we compare plain integers here we use ==, not is; identity was only needed when comparing node objects. No set of seen numbers is required, so this too is O(1) extra space.

Common pitfalls

• Skipping the null checks. The fast pointer reads fast.next.next, which touches two links ahead. Before doing that you must confirm both exist, which is why the loop condition is fast is not None and fast.next is not None. Testing only fast is not None will crash with an AttributeError on the very next line when fast.next is None. Python’s and short-circuits, so ordering the check as fast and fast.next is what keeps the second half from ever running on None.
• Using == instead of is for nodes. To ask whether the two pointers are on the same node, compare identity with slow is fast. Writing slow == fast asks whether two nodes hold equal values, which can be true for different nodes and gives a false cycle report.
• A speed ratio other than one-and-two. Moving the fast pointer three steps at a time breaks the guarantee: the gap can shrink by two per round and jump over zero without the pointers ever landing together. Keep it to one and two.
• Forgetting the empty or single-node list. On head is None or a lone node, the loop body never runs and the functions return correctly, but only because the condition is checked first. Do not move the pointers before the while test.
• Reset-to-head, not to the meeting point. When finding the cycle’s start, it is the head pointer that gets reset while the meeting pointer stays put. Swapping which one moves back breaks the distance argument.

Big-O summary

The constant space is the reason to prefer fast and slow pointers over a set of visited nodes: both find a cycle in linear time, but only the two-pointer version does it without extra memory that grows with the input.

Practice

1. Write middle_node yourself and adjust it to return the first of the two middle nodes on an even-length list instead of the second. Test it on [10, 20, 30, 40] and confirm you get 20, not 30. (Hint: change where the loop stops so slow takes one fewer step.)

2. Write a function cycle_length(head) that returns the number of nodes in the cycle, or 0 if there is none. Once slow and fast meet, keep one of them fixed and walk the other around until it returns, counting the steps. Test it on build_cycle([1, 2, 3, 4, 5], 2) and expect 3.

3. The happy-number rule is one “next value” function; invent another, such as “if even divide by two, if odd triple and add one,” and use fast and slow pointers to detect whether a starting number falls into a loop before reaching 1. Explain in one sentence why a seen-set would also work but cost more memory.