Fast & Slow Pointers

Fast & Slow Pointers

Two pointers move through the same sequence at different speeds, usually one step and two steps at a time. The speed difference turns certain questions into simple arithmetic:

• If the sequence loops back on itself, the fast pointer eventually laps the slow one, and they meet. If it doesn't loop, the fast pointer reaches the end.
• When the fast pointer reaches the end, the slow one has gone exactly half as far, so it's at the middle.

This is also called Floyd's tortoise and hare algorithm. It answers these questions in O(n) time and O(1) extra space, where the obvious alternative (a HashSet of visited nodes) needs O(n) memory.

Detect a cycle in a linked list

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {   // fast checks two steps ahead, so guard both
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;            // same NODE (reference equality), not same value
    }
    return false;                                 // fast fell off the end → no cycle
}

Why they must meet (and can't jump over each other): once both are inside the cycle, look at the gap from fast to slow. Every step, fast gains exactly one position on slow, so the gap shrinks by one each time and eventually reaches zero. Fast can't skip past slow, because the gap decreases by exactly 1, never by 2. It takes at most one full cycle length of steps after slow enters the cycle.

Find where the cycle starts

public ListNode detectCycle(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: they met inside the cycle
            ListNode p = head;                    // phase 2: one from the head, one from the meeting point
            while (p != slow) { p = p.next; slow = slow.next; }
            return p;                             // they meet exactly at the cycle's entrance
        }
    }
    return null;
}

Why phase 2 works. Let a = distance from head to the cycle entrance, b = distance from the entrance to the meeting point, and c = cycle length. When they meet, slow has walked a + b and fast has walked 2(a + b). Fast's extra distance, a + b, must be a whole number of laps: a + b = k·c. So a = k·c − b. Walking a more steps from the meeting point goes k laps minus b, which lands exactly on the entrance. A pointer starting from the head also reaches the entrance after a steps. So they meet there.

Middle of a linked list

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;       // odd length: the exact middle; even length: the SECOND of the two middles
}

If you need the first middle for even lengths (common when splitting a list for merge sort), loop while fast.next != null && fast.next.next != null. Getting this boundary wrong is the classic bug in this pattern.

Palindrome linked list in O(1) space

Combine three techniques: find the middle, reverse the second half in place, then compare the halves from both ends.

public boolean isPalindrome(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

    ListNode second = reverse(slow);          // reverse from the middle to the end
    ListNode p = head, q = second;
    boolean ok = true;
    while (q != null) {
        if (p.val != q.val) { ok = false; break; }
        p = p.next; q = q.next;
    }
    reverse(second);                          // restore the list — good manners for callers
    return ok;
}

private ListNode reverse(ListNode node) {
    ListNode prev = null;
    while (node != null) { ListNode next = node.next; node.next = prev; prev = node; node = next; }
    return prev;
}

Restoring the list afterwards is a detail interviewers notice: a checking function shouldn't leave its input rearranged.

Remove the n-th node from the end: a fixed gap

This is a variation where the pointers move at the same speed but start n apart. When the leading one hits the end, the trailing one is n nodes from the end.

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);   // dummy handles "remove the head" without special cases
    ListNode lead = dummy, trail = dummy;
    for (int i = 0; i <= n; i++) lead = lead.next;       // gap of n+1 → trail stops BEFORE the target
    while (lead != null) { lead = lead.next; trail = trail.next; }
    trail.next = trail.next.next;
    return dummy.next;
}

Cycles that aren't linked lists

Anything where each value determines the next value forms an implicit linked list, and Floyd's algorithm applies.

Happy Number: repeatedly replace a number by the sum of the squares of its digits. It's "happy" if it reaches 1. Unhappy numbers fall into a cycle that never includes 1:

public boolean isHappy(int n) {
    int slow = n, fast = next(n);
    while (fast != 1 && slow != fast) {
        slow = next(slow);
        fast = next(next(fast));
    }
    return fast == 1;
}
private int next(int n) { int s = 0; while (n > 0) { int d = n % 10; s += d * d; n /= 10; } return s; }

Find the Duplicate Number (n+1 values in 1..n, array read-only): treat i → nums[i] as a linked list. The duplicate value is where two arrows point to the same node, which is the cycle's entrance. Apply exactly the detectCycle logic above to indexes.

When to reach for it

• Linked list questions about cycles, the middle, or the k-th node from the end.
• A sequence defined by a function applied repeatedly (x → f(x)) that may loop.
• Any time the natural solution is "remember what I've visited" and the problem demands O(1) space.

Follow-up questions this topic invites — and their answers

Q: Why does fast move two steps and not three? A: With speed 2 against 1, the gap closes by exactly one per step, so the pointers can never skip past each other inside the cycle and are guaranteed to meet within one lap. Other speed pairs also eventually meet, but the "meeting point → entrance" arithmetic used to find the start of the cycle relies on the 2:1 ratio.

Q: How do you find the length of the cycle? A: After the pointers meet, keep one fixed and move the other one step at a time, counting until it returns to the same node. That count is the cycle length.

Q: HashSet or Floyd's: which is better? A: Both are O(n) time. A HashSet of visited nodes is simpler and also finds the cycle start immediately, but uses O(n) memory. Floyd's uses O(1) memory. In interviews, mention the set as the straightforward solution, then give Floyd's when asked to reduce space.

Q: What's a common bug with the middle-node loop? A: Using the wrong loop condition for the list length. while (fast != null && fast.next != null) returns the second middle for even lengths, and while (fast.next != null && fast.next.next != null) returns the first. Splitting for merge sort needs the first middle, otherwise a two-node list never splits and recursion never ends.

Q: Why use a dummy node when removing the n-th from the end? A: If the node to remove is the head, there's no previous node to relink. A dummy node before the head makes every removal look the same, prev.next = prev.next.next, and removes the special case.