Fast/Slow Pointers — Tortoise and Hare, Cycle Detection, Three Walkthroughs

Fast/slow pointers are the third leg of the "two-pointer" umbrella term, and the one most likely to be lost when someone says "two-pointer" without qualification. They don't converge like converging two-pointer and they don't bracket a growing range like sliding window — they walk the same direction at different speeds, and where that difference lands is the answer. Cycle detection, midpoint-finding, and "does this process eventually terminate" all reduce to one seven-line loop.

Recognition — when to reach for it

Fast/slow pointers are the right tool when all four of these hold:

You're traversing a sequential structure — a linked list, an array with nums[i] = f(i) semantics, an implicit state machine — where each element has a well-defined "next".
The question is about cycles, midpoints, or eventual termination — not about pair-finding or range-tracking.
The naïve solution uses O(n) auxiliary space (a visited set or the whole sequence in memory), and the constraints demand O(1).
Two pointers moving at different rates would meet, or land at different meaningful positions, in a way that answers the question.

Cycle detection is the archetypal problem. LC 141 asks "does this linked list contain a cycle?"; LC 142 wants the cycle's start; LC 202 turns "does the happy-number process terminate?" into a graph-cycle-detection question in disguise.

Mental model — the speed differential

Two pointers, slow and fast, both start at the head. Every step: slow advances one, fast advances two. Two possibilities:

No cycle. fast walks off the end (hits null in a linked list, or exceeds bounds). slow and fast never meet.
There is a cycle. fast enters the cycle and laps around it. slow enters the cycle later; once inside, both are trapped in the cycle. fast gains on slow by one step per iteration, so within at most (cycle length) more steps, they collide.

The whole invariant fits in one line: inside a cycle, the fast pointer gains exactly one step per iteration on the slow pointer. Cycle length ≤ n, so collision happens in O(n) steps. Because we hold only two pointers, auxiliary space is O(1).

That's the technique. Every fast/slow variant is a wrinkle on that speed differential.

The template

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

The while condition — fast and fast.next — is the load-bearing safety. Both must be non-None before we dereference fast.next.next. Miss either half and you'll NoneType on a straight-line input.

Three flavours worth naming

Cycle detection. Do they collide? LC 141, LC 202.
Cycle start. They collided — where does the cycle begin? LC 142, LC 287 (Find the Duplicate Number). Floyd's algorithm has a beautiful math argument for this second phase.
Midpoint / kth-from-end. Fast walks twice as fast (or n − k steps ahead), and where slow lands is your answer. LC 876 (Middle of the Linked List), LC 19 (Remove Nth Node from End of List).

The first two share the collision mechanism; the third is a different use of the speed differential entirely.

Walkthrough 1 — LeetCode 141, Linked List Cycle

Return true if the linked list has a cycle.

Recognition. Cycle detection ✓. Linked list ✓. Naïve solution is O(n) space with a visited set. Fast/slow gives O(1).

Approach. Standard template. If fast hits null, no cycle. If slow == fast, cycle.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head: ListNode) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Trace a list 1 → 2 → 3 → 4 → 5 → 2 (5 loops back to 2):

Iteration	slow	fast
0	1	1
1	2	3
2	3	5
3	4	3
4	5	5

slow == fast at iteration 4. Return True.

Notice the trace: fast re-enters the cycle from 5 → 2 → 3 while slow is still climbing 3 → 4. Their positions converge because fast gains one step per iteration inside the cycle.

Walkthrough 2 — LeetCode 142, Linked List Cycle II

Return the node where the cycle begins, or null if none.

The math trick that makes this beautiful:

Run fast/slow until they collide (as in LC 141). Let L = distance from head to cycle start, k = distance from cycle start to the collision point along the cycle, and C = cycle length. When they meet:
- slow walked L + k steps.
- fast walked 2(L + k) steps.
- fast is k steps "ahead" of slow inside the cycle, which means fast has gone around the cycle some integer number of times: 2(L + k) - (L + k) = L + k = mC for some integer m ≥ 1.
So L = mC - k. This means: from the collision point, walking L more steps also gets you back to the cycle start (walking L = mC - k steps around a cycle of length C lands -k mod C, undoing the offset).
So: start a second pointer at head, keep the first at the collision point, advance both one step at a time. When they meet, that's the cycle start.

def detectCycle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Cycle detected. Find the start.
            ptr = head
            while ptr != slow:
                ptr = ptr.next
                slow = slow.next
            return ptr
    return None

Same list 1 → 2 → 3 → 4 → 5 → 2. From the collision at node 5, and a fresh pointer at head (node 1): after 1 step, ptr = 2, slow = 2 (5 → 2 by the cycle edge). They meet at node 2 — the cycle's start.

The math argument is what makes this a favourite whiteboard interview question. You're not expected to derive it live; you're expected to have seen it and be able to explain the "walk L more steps and they meet" claim.

Walkthrough 3 — LeetCode 202, Happy Number

Starting from n, repeatedly replace it with the sum of the squares of its digits. Return true if you reach 1, false if the process cycles.

Not a linked list — but conceptually one. Each number has exactly one "next" (its digit-square-sum). The question "does the process cycle?" is the same as "does this implicit linked list have a cycle?".

def isHappy(n: int) -> bool:
    def next_num(x):
        s = 0
        while x:
            s += (x % 10) ** 2
            x //= 10
        return s

    slow = fast = n
    while True:
        slow = next_num(slow)
        fast = next_num(next_num(fast))
        if fast == 1:
            return True
        if slow == fast:
            return False

Trace n = 19:

19 → 1² + 9² = 82
82 → 8² + 2² = 68
68 → 6² + 8² = 100
100 → 1² + 0² + 0² = 1

slow needs to catch up but fast reaches 1 first — return True.

The clean fast/slow shape works because there's no cycle-of-length-1 pitfall: if fast hits 1, 1 → 1 → 1 → … is technically a self-loop, but fast == 1 triggers the return branch before slow == fast fires.

Common bugs

Off-by-one on the while condition. while fast and fast.next is the correct guard for fast = fast.next.next. Using while fast alone crashes on straight-line inputs.
Starting both at head.next and head instead of both at head. Some tutorials teach the "hare starts one ahead" variant. Both work, but the equal-start version is more general and easier to reason about — stick with it.
Using fast/slow when you don't need cycle-tolerance. For a plain "find the middle of a linked list without a cycle" problem, the fast/slow midpoint works — but a two-pass "count, then walk to the middle" is arguably clearer. Reach for fast/slow when O(1) space or cycle-tolerance matters.
Forgetting to reset the tortoise for LC 142 phase 2. The second walk starts one pointer at head, keeps the other at the collision point. Getting this backwards returns a node inside the cycle rather than the cycle's start.

When fast/slow is not the tool

The structure has branching. Trees, DAGs, general graphs — each node has multiple "next"s. Fast/slow assumes exactly one. For graph cycle detection, use DFS with a recursion-stack marker (see the topological-sort post).
You need to find any cycle in a general structure. Fast/slow finds cycles in sequential structures only. In-general-graph cycle detection is a DFS + colour marker or union-find question.
The naïve O(n) space solution is fine. If the input is small and clarity matters, a visited set is unambiguous and fast enough. Reach for fast/slow when constraints demand O(1) auxiliary.
The problem is about "extend right, contract left" on a contiguous range. That's sliding window, not fast/slow.

How the Algotrek tutor would prompt you here

When a learner opens a fast/slow-pointer problem on Algotrek, the tutor doesn't reveal the template. It asks three questions:

"Is the structure sequential — each element has exactly one next?" — Naming this is what tells you fast/slow applies at all. Trees and graphs are out.
"What does 'collision' mean for your problem?" — Cycle presence, cycle start, or midpoint? Each has the same starting template but a different second half.
"What space budget are you working with?" — If O(n) auxiliary is fine, a visited set is cleaner. Fast/slow's win is O(1). Naming the constraint tells you whether the technique is even worth reaching for.

Answer all three and the template is a five-minute typing exercise. Try the Linked List Cycle lesson on Algotrek to see the prompt-then-reveal flow on the friendliest fast/slow problem.

Where to go next

LC 287, Find the Duplicate Number. LC 142 in disguise on an array. Read nums[i] as a linked-list edge, then run Floyd's. A great study in "same technique, different-looking data structure".
LC 876, Middle of the Linked List. The midpoint flavour. Fast walks twice as fast; when it hits the end, slow is at the middle. One while loop.
LC 19, Remove Nth Node from End of List. Fast walks n steps ahead, then both walk in lockstep. When fast hits the end, slow is at the node before the one to remove. One pass, O(1) space.
LC 143, Reorder List. Uses fast/slow to find the middle, then reverses the second half and interleaves. Composes fast/slow with two other patterns — a fun graduation exercise.

Cross-reference the two-pointer post — converging pointers meet in the middle; fast/slow pointers race one another. Both are "two pointers", both are O(n), but they preserve different invariants. Cross-reference the sliding-window-vs-two-pointer post — this is the "third flavour" the vocabulary confusion is about.

For the O(n) time and O(1) space claim, see the Big-O cheat sheet and the space complexity post.