Fast and slow pointers

Problem

Some questions are about the shape of a sequence you can only walk forward: does it loop, where does the loop start, where is its middle. The obvious answer is to write down every node you visit and stop when you see one twice. That costs memory proportional to the walk. The interview version adds "in constant space", and the answer is to let two walkers carry the memory for you: their distance apart.

Intuition

Two runners start together on a track. If the track is a straight line, the faster one finishes first and that is the end of the story. If the track has a circular section, the faster runner enters it first and goes round, and the slower runner enters later. On a circle, speed differences always become meetings: the faster runner closes the gap by one position per turn, so it cannot jump over the slower one, and sooner or later it catches up from behind. A runner who finishes tells you there is no loop; a meeting tells you there is.

The middle works the same way without a loop. If one pointer moves twice as fast as the other, then at the moment the fast one steps off the end, the slow one has made exactly half as many steps, which is half the list. You never needed to know the length.

The shape the algorithm is analysed on: a tail, then a loop. The last node's arrow returns to node 3, the entrance of the cycle.

Mechanics

Detecting a cycle

Start both pointers at the head. Each turn, slow moves one node and fast moves two. If fast ever reaches the end (it is null, or its next is null), the list is straight and there is no cycle. If slow and fast are ever the same node, there is a cycle.

Why they must meet. After both pointers are inside the loop, say the loop has L nodes. Each turn fast gains exactly one node on slow, so the gap, measured round the loop, shrinks by one per turn. A gap that goes down by one each time from some value under L passes through zero, and zero means they are on the same node. Fast never steps over slow, because the gap would have to skip from 1 to −1, and it only ever changes by exactly one. Slow enters the loop after the tail's 3 nodes, and fast has entered earlier, so they meet within L more turns of slow arriving.

Finding where the cycle begins

Let μ be the number of nodes before the cycle (the tail length) and L the cycle length. When they meet, slow has taken k steps and fast has taken 2k. Both are in the loop and fast has gone round some whole number of extra laps, so 2k − k = k is a multiple of L. Slow's position is k − μ steps past the entrance, and since k is a multiple of L that is the same place as −μ steps past it. So walking μ more steps from the meeting point lands exactly on the entrance, going round the loop as needed.

That gives the second phase. Put one pointer at the head and keep one at the meeting point. Move both one step at a time. The head pointer needs μ steps to reach the entrance, and so does the other, so they meet there, and the place they meet is the answer. It also hands you μ as the number of steps taken and, by walking once round from the entrance, L.

Finding the middle

Same movement, no loop. Stop when fast has no node or no next node. For a list of length n, slow is then at index ⌊n / 2⌋: the exact middle when n is odd and the second of the two middles when n is even. If you test fast.next and fast.next.next instead, slow stops one node earlier on even lengths, at the first middle. Which one you want depends on whether the first half should be the longer one when you split.

Each row is one turn on the list from the first diagram. Fast gains one node per turn on the loop, so the gap from fast to slow closes steadily until the green cell where they coincide.

Worked example

Cycle detection and entrance. The list has 8 nodes numbered 0 to 7, and the last one points back to node 3. Phase one races the pointers:

They meet at node 5 after 5 turns, which is a multiple of the cycle length 5, as the argument predicts. Phase two puts one pointer on the head and one on the meeting point and moves both a node at a time:

After 3 steps both are at node 3: the cycle begins at node 3, the tail has 3 nodes and the loop has 5.

An array as a linked list. Take [3, 1, 3, 4, 2]. Treat index i as a node whose next node is index nums[i]. Starting from index 0 the pointers visit:

They meet at index 2. Restarting one pointer from index 0 and walking both by one, they meet again at index 3 after 1 step. The entrance is 3, and that is the repeated value, because two different indices (0 and 2) both hold 3 and so both point at it.

Finding the middle. For a list of 7 nodes the pointers stop with slow at index 3; for 6 nodes slow stops at index 3, the second of the two middles:

Implementation

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False


def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            break
    else:
        return None                               # fast fell off the end
    slow = head
    while slow is not fast:
        slow, fast = slow.next, fast.next
    return slow


def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow


def find_duplicate(nums):
    slow = fast = 0
    while True:
        slow, fast = nums[slow], nums[nums[fast]]
        if slow == fast:
            break
    slow = 0
    while slow != fast:
        slow, fast = nums[slow], nums[fast]
    return slow


def is_happy(n):
    def step(x):
        return sum(int(d) ** 2 for d in str(x))

    slow, fast = n, step(n)
    while fast != 1 and slow != fast:
        slow, fast = step(slow), step(step(fast))
    return fast == 1

find_duplicate uses a do-while shape because the pointers start equal, so the first check must come after the first move. Index 0 is a safe start: every value is at least 1, so nothing points back at index 0, which makes it part of the tail and guarantees the entrance is a real repeated value.

Variations and edge cases

• Palindrome list. Find the first middle (while fast.next and fast.next.next), reverse the list after it, then compare the two halves node by node. Reverse the second half back afterwards if the problem says not to damage the input.
• Reorder list. Split at the first middle, reverse the second half, then weave: first, last, second, second to last, and so on. This is three earlier patterns in a row: find the middle, reverse, merge.
• Cycle length. After they meet, hold one pointer still and count steps until the other returns to it. Here that count is 5.
• Happy number. The "list" is the sequence of digit-square sums. It cannot grow forever, because the sum of squared digits of a large number is far smaller than the number, so it either reaches 1 (which maps to itself) or repeats.
• A set is fine too. A hash set of visited nodes is simpler and runs in O(n) time and space. Say that first in an interview, then offer Floyd's version when asked for constant space.
• Edge cases: an empty list, a single node (with and without a self-loop), two nodes, a cycle that includes the head (the entrance is the head, phase two takes zero steps), a straight list such as 1 → 2 → 3 → 4, where fast falls off the end after 1 turn, and comparing nodes with is, not values, because two different nodes can hold equal values.

Complexity and tradeoffs

• Time: O(n). Slow enters the loop after μ steps, and fast catches it within L more, so detection is at most μ + L turns, each constant work. Phase two adds at most μ steps. In the example that was 5 turns plus 3 steps for 8 nodes.
• Space: O(1), two pointers. This is the whole point; a visited set is O(n).
• Baseline. Marking visited nodes (a set, or a flag written into the node) is also O(n) time but spends memory, or modifies the input.
• When it fails. The sequence must be a deterministic function of the current item, since the argument depends on two walkers following the same path. If steps depend on history, or the structure is a graph where each node has several successors, there is no single "next", and you use a visited set with depth-first search. Because the values lie in 1..n, binary search on the value range (counting the elements at most mid) can also find the duplicate in O(n log n) without changing the array; Floyd gets O(n).
• Constants. Fast does about twice the moves of slow, so it makes roughly three times as many pointer steps as a single walker. Brent's variant, in the references, reduces that.

Problems

The home problems are the four things two speeds can do: detect a loop (linked list cycle, happy number), find where a loop starts through an array of indices (find the duplicate number), find the middle (middle of the linked list), and split a list at the middle to finish with another technique (palindrome list, reorder list). Remove nth from the end, rotate list and sort list reuse the idea with a fixed gap or a midpoint split.

Easy

• 141. Linked List Cycle Blind 75 Grind 169 NeetCode 150 NeetCode 250
  A pointer moving two steps per turn eventually laps a pointer moving one if and only if the list has a cycle.
• 202. Happy Number NeetCode 150 NeetCode 250
  Repeatedly summing squared digits either reaches 1 or enters a cycle, which Floyd's two pointers or a seen-set will detect.
• 234. Palindrome Linked List Grind 169
  Find the middle, reverse the second half and compare it against the first half node by node.
• 876. Middle of the Linked List Grind 169
  When the fast pointer reaches the end, the slow pointer is in the middle.

Medium

• 143. Reorder List Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Find the middle, reverse the second half, then weave the two halves together one node at a time.
• 287. Find the Duplicate Number Grind 169 NeetCode 150 NeetCode 250
  Read each value as a pointer to an index; the duplicate is the entrance of the cycle that Floyd's algorithm finds.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 19. Remove Nth Node From End of List Medium
• 61. Rotate List Medium
• 148. Sort List Medium

Connections

This page is the linked-list version of the same-direction two-pointer idea: two indices on one sequence, one moving faster, with the gap between them carrying information. The fixed-gap pointers that remove the nth node from the end are the cousin where the gap stays constant instead of growing. Reorder list is the first problem where three earlier techniques combine, so it is a good check on the reversing and merging moves from the basics page.

Check yourself

References

• Knuth, The Art of Computer Programming, volume 2, section 3.1, exercises on cycle detection: the source of the two-speed algorithm, credited there to Robert W. Floyd.
• Brent, "An improved Monte Carlo factorization algorithm", BIT 20 (1980): a faster cycle-finding variant that moves one pointer in power-of-two jumps.
• Pollard, "A Monte Carlo method for factorization", BIT 15 (1975): the rho method, which applies cycle detection to the sequence a function generates.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 10.2: linked lists, the setting for the cycle questions.
• Sedgewick and Wayne, Algorithms, section 1.3: linked-list implementations and their pointer manipulations.
• Skiena, The Algorithm Design Manual: pointer-based structures and the tradeoffs against arrays.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.