Fast and Slow Pointers: The Core Idea

Two pointers start at the same place and move through the same sequence. One takes one step at a time. The other takes two. Where they end up, and whether they ever land on the same spot, answers the question.

That is the whole pattern. It sounds too simple to be useful, but it answers three questions that otherwise need extra memory: does this linked list loop forever, where does the loop begin, and where is the middle of a list whose length you do not know.

The intuition: two runners on a track

Picture two runners on a road that ends in a circular track. One runs twice as fast as the other. If the road simply ends, the fast runner reaches the end first and the race is over. If the road leads into a loop, both runners end up going round and round, and the fast one must eventually come up behind the slow one and pass the same point at the same moment.

So the question "is there a loop?" becomes "do the runners ever meet?". You need to remember nothing about where they have been. Two positions are enough.

How to recognise it

Look for these signals in the problem statement and the constraints.

• Cycle questions. "Does this list have a cycle?" "Where does the cycle start?" Anything that asks whether following next-pointers loops forever.
• Middle in one pass. A linked list has no length field. When the fast pointer reaches the end, the slow pointer has taken half as many steps, so it is in the middle.
• A sequence of states that might repeat. If a process turns each state into exactly one next state, and there are only finitely many states, the process must repeat a state. That is a cycle, even when no linked list is in sight. Happy Number and Find the Duplicate Number are both this.
• "Use O(1) extra space." This is the loudest signal. The obvious cycle detector is a hash set of visited nodes, which costs O(n) memory. Forbidding that memory tells you to use this pattern.

The obvious answer is worth writing out, because it is correct and it is what you improve on:

1def has_cycle_with_set(head: ListNode | None) -> bool:2    """Remember every node visited; seeing one again means a cycle."""3    seen: set[ListNode] = set()4    node = head5    while node is not None:6        if node in seen:7            return True8        seen.add(node)9        node = node.next10    return False

It runs in O(n) time, which is already optimal. The cost is O(n) space: on a list of ten million nodes the set holds ten million references, often hundreds of megabytes. Fast and slow pointers get the same answer with two variables.

How it works: why the pointers must meet

Once both pointers are inside the cycle, measure the gap: the number of steps the fast pointer needs to reach the slow one, going forward round the cycle.

Each tick, slow moves 1 and fast moves 2. So the gap shrinks by exactly 1 every tick. A whole number that goes down by exactly one each step cannot jump over zero. It must hit zero, and zero means they are on the same node. It takes fewer than L ticks, where L is the cycle length, because the gap starts below L.

If there is no cycle, the fast pointer falls off the end and the loop stops. Meeting, or reaching the end, are the only two outcomes.

A run makes it concrete. Take 1 → 2 → 3 → 4 → 5 → 6, where node 6 points back to node 3.

They meet at node 5. That is not where the cycle starts. Node 3 is.

How it works: finding the entrance

Name three distances:

• a = steps from the head to the cycle entrance. Here 1 → 2 → 3, so a = 2.
• L = the cycle length. Here 3 → 4 → 5 → 6 → 3, so L = 4.
• b = steps from the entrance to the meeting point. Here 3 → 4 → 5, so b = 2.

When they meet, slow has taken a + b steps. Fast has taken twice as many. Fast walked the same road plus some whole number k of extra laps:

fast steps  = 2 × slow stepsa + b + kL  = 2(a + b)        kL  = a + b         a  = kL − b

Read the last line as an instruction. Walking a steps forward from the meeting point means walking kL − b steps round the cycle: the L − b steps that finish the current lap, then k − 1 full laps. That lands exactly on the entrance. Walking a steps from the head also lands on the entrance, by the definition of a.

So: put one pointer back at the head, leave the other at the meeting point, and move both one step at a time. They meet at the entrance. Check it: from node 5, two steps go 5 → 6 → 3. From the head, two steps go 1 → 2 → 3. Both reach node 3.

Why the speeds are 1 and 2

A common interview question is "what if fast moved three steps?". Starting from the same node, two pointers with different speeds do still meet eventually. But two things break. The simple proof goes, because the gap now closes by 2 per tick and can jump from 1 to −1 on a lap. And the entrance arithmetic changes: with a 3-to-1 ratio you get 2(a + b) = kL, not a + b = kL, so the reset trick lands on the wrong node. On a = 2, L = 4, the reset loop never ends at all. Keep 1 and 2.

Variants: the three forms

All three run the same loop. They differ only in what happens inside it and what you return.

The templates

Every template in this section uses this node class:

1class ListNode:2    def __init__(self, val: int = 0, next: "ListNode | None" = None) -> None:3        self.val = val4        self.next = next

Template 1: detect a cycle.

1def has_cycle(head: ListNode | None) -> bool:2    """Floyd's algorithm: O(n) time, O(1) space."""3    slow = fast = head4    while fast is not None and fast.next is not None:5        slow = slow.next            # one step6        fast = fast.next.next       # two steps7        if slow is fast:            # same node object, not equal values8            return True9    return False                    # fast reached the end: no cycle

The guard fast is not None and fast.next is not None covers both ways of reaching the end. On an even-length list fast lands on None; on an odd-length list fast lands on the last node, whose next is None. Both must be tested, in that order. The comparison uses is, because two different nodes can hold the same value.

Template 2: find the entrance.

1def detect_cycle(head: ListNode | None) -> ListNode | None:2    """Return the node where the cycle begins, or None. O(n) time, O(1) space."""3    slow = fast = head4    while fast is not None and fast.next is not None:5        slow = slow.next6        fast = fast.next.next7        if slow is fast:                 # phase 1: they met inside the cycle8            walker = head                # phase 2: one pointer back to the head9            while walker is not slow:10                walker = walker.next     # both move ONE step11                slow = slow.next12            return walker13    return None

Phase 1 is Template 1. Phase 2 is the a = kL − b result turned into code.

Template 3: find the middle.

1def middle_node(head: ListNode | None) -> ListNode | None:2    """One pass: when fast reaches the end, slow is in the middle."""3    slow = fast = head4    while fast is not None and fast.next is not None:5        slow = slow.next6        fast = fast.next.next7    return slow            # for an even length, this is the SECOND middle

For an even-length list there are two middles, and the loop condition picks one. while fast and fast.next stops on the second middle: on [1, 2, 3, 4] it returns 3. while fast.next and fast.next.next stops on the first middle, 2, which is the end of the first half. Splitting a list in two (Palindrome Linked List, Reorder List) wants the first one. That second form reads fast.next straight away, so check for an empty list before you use it.

Complexity

All three templates run in O(n) time and O(1) space. Without a cycle, fast reaches the end after about n/2 ticks. With a cycle, slow enters it after a ticks, and the gap then closes within fewer than L more ticks, so phase 1 takes fewer than a + L ≤ n ticks. Phase 2 takes exactly a more. The only memory is two or three pointer variables.

Where it goes wrong

Four bugs cover almost every failure. Two crash and two return wrong answers.

1. Checking fast.next before fast. while fast.next is not None and fast is not None reads fast.next before knowing fast exists. It crashes on the empty list, which is the first input a grader tries.
2. Returning the meeting point as the entrance. In the run above they met at node 5 but the cycle begins at node 3. This bug passes every test where the cycle starts at the head, because then a = 0 and the meeting point really is the entrance.
3. Moving fast two steps in phase 2. The derivation says both pointers travel a steps. Doubling one breaks the equality, and the loop lands on the wrong node or never ends.
4. Comparing values instead of nodes. slow.val == fast.val reports a "cycle" in 5 → 7 → 5 → 9 → 5 → None: after two ticks slow is on the second 5 and fast on the third, two different nodes with equal values.

When a solution misbehaves, write the trace table by hand: tick, slow, fast. Four or five rows usually show the fault. If the program hangs, look at the loop condition first. A hang here means a pointer stopped moving, not a slow algorithm.