Floyd's Cycle Detection: Why Fast and Slow Pointers Must Meet

Detecting a loop in a linked list is easy if you are allowed memory: remember every node you have visited and stop at the first repeat. The interview version asks for the same answer in constant space, and the accepted solution — one pointer moving one step, another moving two — is short enough to memorise and strange enough to forget.

This article is about the two things that make it trustworthy: why the pointers are guaranteed to meet, and why a second walk from the head lands exactly on the node where the loop begins.

The problem it solves

Given the head of a singly linked list, decide whether following next ever runs off the end or goes round forever. Follow-ups ask where the loop starts and how long it is.

The same structure hides in problems that never mention a list. Any function that maps a finite set to itself — "next number is the sum of the squares of the digits", "follow the value as an index" — produces a path that must eventually repeat, so it has a tail and a loop, exactly like a list with a cycle.

The intuition

Start both pointers at the head. slow moves one node per step, fast moves two.

If the list has an end, fast reaches it first, and that is the proof of "no cycle".

If there is a loop, both pointers eventually enter it and can never leave. From that moment, look only at the gap between them, measured along the loop in the direction of travel. Each step, fast moves two and slow moves one, so the gap shrinks by exactly one. A gap that shrinks by one each step cannot jump from 1 to −1; it has to pass through 0. That is the meeting — fast cannot leapfrog slow, because it only gains one node per step.

How long can that take? Once slow enters the loop, the gap is less than the loop's length, so they meet before slow completes one lap. In total, slow walks at most as many steps as there are nodes.

Finding where the loop begins

Say the tail before the loop has μ nodes and the loop has λ. When they meet, slow has taken k steps and fast 2k. The extra k steps fast took were spent going round the loop, so k is a multiple of λ.

Now slow is k − μ steps into the loop. Walk it μ more and it is k steps in — a whole number of laps — which is the loop's first node. And a fresh pointer starting at the head also needs exactly μ steps to reach that node. So: put one pointer at the head, leave the other at the meeting point, move both one step at a time, and they meet at the entry. No μ or λ is ever computed.

Watch it run

The animation uses a three-node list twice. First it is straight: fast runs out of list and the answer is "no cycle". Then the last node is pointed back at the second, and the same two pointers go round until fast lands on slow.

The code

Detection, the entry point and the loop length, on a list where node 6 links back to node 3:

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

def build(values, loop_to=None):        # loop_to: index the tail links back to
    nodes = [Node(v) for v in values]
    for a, b in zip(nodes, nodes[1:]):
        a.next = b
    if nodes and loop_to is not None:
        nodes[-1].next = nodes[loop_to]
    return nodes[0] if nodes else None

def meet(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return slow                 # fast lapped slow: there is a loop
    return None                         # fast ran off the end: no loop

def cycle_start(head):
    m = meet(head)
    if m is None:
        return None
    a, b = head, m                      # same distance from here to the entry
    while a is not b:
        a, b = a.next, b.next
    return a

def cycle_length(head):
    m = meet(head)
    if m is None:
        return 0
    n, p = 1, m.next
    while p is not m:
        n, p = n + 1, p.next
    return n

head = build([1, 2, 3, 4, 5, 6], loop_to=2)          # 6 links back to 3
print(meet(head).value, cycle_start(head).value, cycle_length(head))   # 5 3 4
print(meet(build([1, 2, 3])))                        # None

They meet at 5, which is two steps from the entry — and the head is also two steps from the entry, as the proof promised.

The check below compares against the memory-hungry version on 5,000 random lists, with and without loops, and also tests the step bound from the intuition:

import random

def start_with_set(head):              # the O(n)-memory answer to check against
    seen, p = set(), head
    while p is not None and id(p) not in seen:
        seen.add(id(p))
        p = p.next
    return p                            # first node seen twice, or None

def slow_steps(head):
    slow = fast = head
    steps = 0
    while fast and fast.next:
        slow, fast, steps = slow.next, fast.next.next, steps + 1
        if slow is fast:
            return steps
    return None

random.seed(4)
ok, within = True, True
for _ in range(5000):
    n = random.randint(0, 30)
    loop = random.randrange(n) if n and random.random() < 0.7 else None
    head = build(list(range(n)), loop)
    ok &= cycle_start(head) is start_with_set(head)
    ok &= cycle_length(head) == (n - loop if loop is not None else 0)
    if loop is not None:
        within &= slow_steps(head) <= n     # tail + loop = n nodes in total
print(ok, within)                                    # True True

The same trick without a list

An array of n + 1 values, each between 1 and n, must contain a repeat. Read each value as "go to that index" and the array becomes a list whose loop entry is the duplicate: two different indices point at it.

def find_duplicate(nums):              # n + 1 values, each in 1..n
    slow = fast = nums[0]
    while True:
        slow, fast = nums[slow], nums[nums[fast]]
        if slow == fast:
            break
    a, b = nums[0], slow
    while a != b:
        a, b = nums[a], nums[b]
    return a

print(find_duplicate([1, 3, 4, 2, 2]))               # 2

random.seed(9)
ok = True
for _ in range(3000):
    n = random.randint(1, 20)
    nums = list(range(1, n + 1)) + [random.randint(1, n)]
    random.shuffle(nums)
    ok &= find_duplicate(nums) == max(set(nums), key=nums.count)
print(ok)                                            # True

No sorting, no set, and the input is never modified.

The complexity

O(n) time: slow takes at most n steps before meeting, the entry walk at most μ more, and measuring the loop at most λ. O(1) extra memory — two pointers — against O(n) for the visited-set version. That memory difference is the entire reason the question exists.

Where it goes wrong

• Guarding only fast. With while fast: alone, an odd-length straight list crashes: fast lands on the last node and fast.next.next dereferences None. The condition must be fast and fast.next.
• Comparing values instead of nodes. Two nodes can hold the same value. Use is, not ==.
• Testing for a meeting before moving. Both pointers start at the head; check after the first move, or every list "has a cycle".
• Moving the second phase at different speeds. The entry walk moves both pointers one step at a time. Keeping fast at two breaks the argument.

The entry-point walk has its own lesson: find the cycle start.

How to say it in an interview

"Slow moves one, fast moves two. If there's an end, fast hits it. If there's a loop, once both are inside, the gap between them shrinks by exactly one per step, so fast can't skip over slow — they meet within one lap. That's O(n) time and O(1) space. To find the entry, I reset one pointer to the head and step both by one; the tail length and the distance from the meeting point to the entry are equal modulo the loop length, so they meet at the entry."

The "gap shrinks by one" sentence is the one to say first. It answers the question every interviewer is waiting to ask: why can't fast jump over slow?