Fast & slow pointers

How does Fast & slow pointers work?

Start both pointers at the head. One moves a single step per round, the other moves two.

Step them together inside one loop. Stop when the fast one runs off the end.

If the list ends, there is no cycle. A null next is the proof.

If a cycle exists, the fast pointer laps the slow one. They land on the same node.

Inside the cycle the gap shrinks by one each round. So a meeting is guaranteed.

When the fast pointer reaches the end, the slow one sits at the middle. That gives the midpoint free.

Sources: Wikipedia: Cycle detection

1. slow = 1, fast = 1The list is 1 to 5. Both pointers start at the head.
2. slow = 2, fast = 3One step against two. The gap is one node.
3. slow = 3, fast = 5The gap is now two. The fast pointer is nearly out.
4. fast.next is nullThe list ended, so there is no cycle.
5. slow = 3The slow pointer sits on the middle node. Five nodes, middle is third.

function hasCycle(head) {
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
}

interface ListNode {
    val: number;
    next: ListNode | null;
}

function hasCycle(head: ListNode | null): boolean {
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
        slow = slow!.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
}

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

function hasCycle(?Node $head): bool {
    $slow = $head;
    $fast = $head;
    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
        if ($slow === $fast) return true;
    }
    return false;
}

    public static boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static bool HasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

    public class ListNode {
        public int val;
        public ListNode next;
    }

A worked example of Fast & slow pointers

Where the cycle starts

A linked list may loop back into itself somewhere. Return the node where that loop begins.

If the list has no loop, return null.

First let the slow and fast pointers meet inside the loop.

Then move one pointer back to the head. Step both one at a time, and they meet at the entry.

function detectCycle(head) {
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            // head to entry is the same distance as meeting point to entry
            let walker = head;
            while (walker !== slow) {
                walker = walker.next;
                slow = slow.next;
            }
            return walker;
        }
    }

    return null;
}

When should you use Fast & slow pointers?

Use Fast & slow pointers when the problem statement says “detect a cycle in a linked list”, “find where a cycle begins” or “find the middle node of a list”. A solution built on it usually runs in O(n).

• •detect a cycle in a linked list
• •find where a cycle begins
• •find the middle node of a list
• •determine if a list is a palindrome
• •no extra memory / O(1) space, only pointers

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Fast & slow pointers confused with?

Fast & slow pointers is most often confused with Two pointers (same direction), Hash set / map, Linked list reversal and Graph BFS / DFS.

• Two pointers (same direction): There one pointer reads and the other writes. Here both read, at different speeds.
• Hash set / map: A set of visited nodes also catches a cycle. It costs O(n) memory instead of O(1).
• Linked list reversal: Reversal rewires the links themselves. This pattern never changes a pointer in the list.
• Graph BFS / DFS: A traversal finds cycles in any graph, with a visited set. This works because each node has one exit.

Common mistakes with Fast & slow pointers

• Checking only fast in the loop condition

  Reading fast.next.next throws when fast.next is null. Test both before stepping.

• Starting the two pointers apart

  A head start changes which node they meet on. The entry proof assumes the same start.

• Comparing values instead of nodes

  Two different nodes can hold the same value. Compare the references themselves.

• Treating the meeting point as the entry

  The two pointers meet somewhere inside the loop, not at its start. A second walk finds the entry.

Which interview problems use Fast & slow pointers?

Interview problems solved with Fast & slow pointers include Linked list cycle, Linked list cycle II, Middle of the linked list, Happy number, Find the duplicate number, Palindrome linked list and Remove nth node from the end.

• Linked list cycle: The meeting itself is the whole answer.
• Linked list cycle II: A second walk from the head finds where it enters.
• Middle of the linked list: When fast ends, slow is standing on the middle.
• Happy number: The digit-square step builds an invisible linked list.
• Find the duplicate number: The array values act as next pointers.
• Palindrome linked list: Find the middle, reverse the back half, compare.
• Remove nth node from the end: A fixed gap instead of a doubled speed.

What is the time and space complexity of Fast & slow pointers?

The target complexity of Fast & slow pointers is O(n).

n up to 1e6 gives O(n) time and O(1) space. The slow pointer never walks more than n steps.