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.

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;
}

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?

These phrases in a problem statement point here:

• •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

What is Fast & slow pointers confused with?

• 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

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

Which interview problems use Fast & slow pointers?

• 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?

O(n)

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