Fast & Slow Pointers

At a glance

The instinct

Whenever something moves by a deterministic rule - node.next, "replace n by the sum of the squares of its digits", "jump to index nums[i]" - the path either reaches an end or falls into a loop. A hash set of visited states would detect the loop, but costs O(n) memory. Floyd's tortoise and hare does it with two variables: one walker moves one step, the other two steps. If there is a loop the fast one must eventually catch the slow one from behind; if there is an end, the fast one finds it first. The same speed ratio also stops the slow pointer exactly at the middle of a list.

Recognise it

Not this pattern if...

• The array is sorted and you are looking for a pair or squeezing from both ends - that is opposite-direction two pointers.
• You need the start of every cycle in a general graph with many outgoing edges - use DFS colouring.
• You must remove a node k from the end - that is a fixed-gap pointer, covered under linked list techniques.

Memory hack

Analogy: two runners on a running track with an entrance tunnel. The tunnel has length a, the oval has length L. When they meet, the distance back from the meeting point to the tunnel exit equals the tunnel length (modulo laps).

Say it out loud in the interview:

1. "What is my next function, and can it ever be null?"
2. "Phase 1: slow += 1, fast += 2 until they meet or fast hits the end."
3. "Phase 2 if I need the entrance: one pointer to head, both move by 1, meeting point is the start."

How it works

Let a be the distance from the head to the cycle entrance and L the cycle length. Each round the gap between hare and tortoise grows by exactly 1, so once both are inside the cycle the hare closes the distance one node at a time and cannot jump over the tortoise.

At the meeting point the tortoise has walked a + b (plus some full laps) and the hare twice that. Subtracting shows a is a whole number of laps minus b, so a pointer that starts at the head and one that starts at the meeting point, both moving one step at a time, reach the entrance at the same moment.

flowchart TD
    A[slow = head, fast = head] --> B{"fast and fast.next not null?"}
    B -- no --> C[No cycle - slow is at the middle]
    B -- yes --> D[slow = next of slow, fast = next of next of fast]
    D --> E{slow == fast?}
    E -- no --> B
    E -- yes --> F[Cycle found]
    F --> G[ptr = head; move ptr and slow one step each]
    G --> H{ptr == slow?}
    H -- no --> G
    H -- yes --> I[ptr is the cycle entrance]

Middle trace on 1 2 3 4 5: slow/fast go (1,1) -> (2,3) -> (3,5); fast.next is null, so slow = 3. On 1 2 3 4 they go (1,1) -> (2,3) -> (3,null) and slow = 3, the second middle.

Java template

import java.util.function.IntUnaryOperator;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

class FastSlow {
    // Middle node (second middle for even length).
    static ListNode middle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // Cycle entrance, or null if the list ends.
    static ListNode cycleStart(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {                 // phase 1 done: inside the loop
                ListNode ptr = head;
                while (ptr != slow) {           // phase 2: equal speed from head and meeting point
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }

    // Same idea on an implicit sequence x -> f(x) that never ends (always has a cycle).
    static int implicitCycleStart(int start, IntUnaryOperator f) {
        int slow = f.applyAsInt(start), fast = f.applyAsInt(f.applyAsInt(start));
        while (slow != fast) {
            slow = f.applyAsInt(slow);
            fast = f.applyAsInt(f.applyAsInt(fast));
        }
        int ptr = start;
        while (ptr != slow) {
            ptr = f.applyAsInt(ptr);
            slow = f.applyAsInt(slow);
        }
        return ptr; // e.g. Find the Duplicate Number: start = 0, f = i -> nums[i]
    }
}

Complexity

Variations

• Cycle detection - boolean answer only: Linked List Cycle.
• Cycle entrance - add phase two: Linked List Cycle II.
• Middle finder - stop when fast runs out: Middle of the Linked List; the first step of Palindrome Linked List and Reorder List.
• Implicit sequence - the "list" is a function on numbers: Happy Number.
• Array as a linked list - indices are nodes, values are next pointers: Find the Duplicate Number.
• Cycle length - after meeting, keep slow fixed and count steps until fast returns.
• Circular array loop - fast/slow over indices with direction checks: Circular Array Loop.

Common mistakes

• Comparing slow == fast before moving them when both start at head, which reports a cycle immediately.
• In phase two, moving the reset pointer two steps at a time instead of one.
• Comparing node values instead of node references - duplicates in values give false positives.
• Picking the wrong middle: if you need the first middle of an even list, start fast at head.next.
• For Find the Duplicate Number, starting at index 1 instead of 0 - index 0 is the only node nothing points to, so it is the true "head".

All practice problems

4 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.