Fast and Slow Pointers

Some problems hand you a sequence with no fixed end — a linked list that might loop back on itself, or a number sequence defined by “apply this function again.” You can’t just check if visitedif visited without extra memory. Fast and slow pointers (Floyd’s Tortoise and Hare) solve this with two pointers moving through the same structure at different speeds — no extra memory, no hash set.

What you’ll learn

Floyd’s Tortoise and Hare: why a fast pointer laps a slow one inside a cycle, guaranteeing they meet.
Cycle detection, and the follow-up trick that finds where the cycle starts.
Finding the middle of a linked list in one pass.
The Happy Number problem — the exact same pattern, no linked list in sight.
The cue: “does this ever repeat/loop” without room for a visited set.

The pattern

One pointer (slowslow) moves one step at a time. The other (fastfast) moves two steps at a time. If the sequence loops, fastfast will eventually lap slowslow and they land on the same node — if it doesn’t loop, fastfast simply runs off the end first.

fast_slow_template.py

def has_cycle_template(get_next, start):
    """get_next(node) returns the next node/state in the sequence."""
    slow = fast = start
    while fast is not None and get_next(fast) is not None:
        slow = get_next(slow)                    # 1 step
        fast = get_next(get_next(fast))           # 2 steps
        if slow is fast:
            return True
    return False
 
 
# example: a simple linked-list-like chain expressed as a dict
graph = {1: 2, 2: 3, 3: 4, 4: 2}   # 4 points back to 2 -> cycle
print(has_cycle_template(lambda n: graph.get(n), 1))

fast_slow_template.py

def has_cycle_template(get_next, start):
    """get_next(node) returns the next node/state in the sequence."""
    slow = fast = start
    while fast is not None and get_next(fast) is not None:
        slow = get_next(slow)                    # 1 step
        fast = get_next(get_next(fast))           # 2 steps
        if slow is fast:
            return True
    return False
 
 
# example: a simple linked-list-like chain expressed as a dict
graph = {1: 2, 2: 3, 3: 4, 4: 2}   # 4 points back to 2 -> cycle
print(has_cycle_template(lambda n: graph.get(n), 1))

How it works

Think of it as two runners on the same circular track: the fast runner gains one lap position on the slow runner every step. Once the slow pointer is anywhere inside the cycle, the fast pointer is guaranteed to close the gap and land exactly on it within one full lap — it cannot “jump over” the slow pointer because it only gains one position at a time.

diagram Cycle detection: fast pointer laps the slow one mermaid

  graph LR
    A["1"] --> B["2"]
    B --> C["3"]
    C --> D["4"]
    D --> B
    S["slow (1 step/iter)"] -.-> B
    F["fast (2 steps/iter)"] -.-> D

sketch Tortoise and hare moving around a cyclic chain p5.js

slow moves one node per tick, fast moves two -- inside the cycle, fast steadily closes the gap until both land on the same node.

Worked example

Linked List Cycle. Exactly the template above, applied to a real linked list.

linked_list_cycle.py

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
 
 
def build_with_cycle(values, cycle_at=None):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if cycle_at is not None:
        nodes[-1].next = nodes[cycle_at]
    return nodes[0]
 
 
def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
 
 
clean = build_with_cycle([1, 2, 3, 4])
looped = build_with_cycle([1, 2, 3, 4], cycle_at=1)
print("clean:", has_cycle(clean))
print("looped:", has_cycle(looped))

linked_list_cycle.py

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
 
 
def build_with_cycle(values, cycle_at=None):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if cycle_at is not None:
        nodes[-1].next = nodes[cycle_at]
    return nodes[0]
 
 
def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
 
 
clean = build_with_cycle([1, 2, 3, 4])
looped = build_with_cycle([1, 2, 3, 4], cycle_at=1)
print("clean:", has_cycle(clean))
print("looped:", has_cycle(looped))

Happy Number. No linked list at all — the “next state” is “sum of squares of digits.” A number is happy if this sequence reaches 1; unhappy numbers cycle forever instead, so cycle detection tells you which.

happy_number.py

def next_value(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total
 
 
def is_happy(n):
    slow = fast = n
    while True:
        slow = next_value(slow)
        fast = next_value(next_value(fast))
        if fast == 1:
            return True
        if slow == fast:            # cycle found, and it's not at 1
            return False
 
 
print(is_happy(19))   # expect True   (19 -> 82 -> 68 -> 100 -> 1)
print(is_happy(2))    # expect False  (loops without ever hitting 1)

happy_number.py

def next_value(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total
 
 
def is_happy(n):
    slow = fast = n
    while True:
        slow = next_value(slow)
        fast = next_value(next_value(fast))
        if fast == 1:
            return True
        if slow == fast:            # cycle found, and it's not at 1
            return False
 
 
print(is_happy(19))   # expect True   (19 -> 82 -> 68 -> 100 -> 1)
print(is_happy(2))    # expect False  (loops without ever hitting 1)

Same two speeds, different question: when fastfast reaches the end, slowslow is sitting exactly at the middle — because slowslow has covered half the distance fastfast has.

python

def middle_node(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow   # middle node (second middle if length is even)

python

def middle_node(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow   # middle node (second middle if length is even)

Time and space complexity

Operation	Time	Space
Cycle detection (hash-set of visited nodes)	$O(n)$	$O(n)$
Cycle detection (fast/slow pointers)	$O(n)$	$O(1)$
Find middle / cycle start (fast/slow)	$O(n)$	$O(1)$

The whole point of this pattern is trading the hash set’s $O(n)$ memory for $O(1)$ — same time complexity, none of the extra space.

When to use it

Cue in the problem	Why fast/slow fits
“does this linked list have a cycle”	Direct application
“find the start of the cycle”	Meet, then reset + walk together
“find the middle of a linked list”	fast reaches end when slow is at middle
“does this number sequence eventually repeat/reach 1”	Happy Number-style, no list needed
“find the duplicate number without extra space”	Treat array values as a linked list via indices

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 141 — Linked List Cycle · Easy

Problem. Return TrueTrue if the linked list contains a cycle.

Constraints. 0 <= number of nodes <= 10^40 <= number of nodes <= 10^4. Can you do it in $O(1)$ memory?

Examples. [3,2,0,-4][3,2,0,-4] with the tail linked to index 1 gives TrueTrue · [1][1] with no cycle gives FalseFalse

Editorial

If a cycle exists, the fast pointer enters it first and then gains one position on the slow pointer per step, so the gap shrinks by one each time and must reach zero — they collide. Without a cycle, fast reaches the end.

Time $O(n)$ . Space $O(1)$ — which is the whole point, since a visitedvisited set solves it trivially at $O(n)$ space.

Two details:

while fast and fast.nextwhile fast and fast.next. Both are needed, because the step is fast.next.nextfast.next.next. Checking only fastfast raises AttributeErrorAttributeError on the last node.
slow is fastslow is fast, not slow.val == fast.valslow.val == fast.val. Values may repeat, so value equality reports false cycles. The habit matters even though this problem’s tests may not punish it.

Follow-ups: “Find where the cycle starts (LC 142)?” — next problem. “Cycle length?” — once they meet, keep one still and walk the other until it returns. “Why must they meet rather than skip past?” — the gap decreases by exactly one per step, so it cannot jump over zero. “Faster than 2x speed?” — still works, but the proof is less clean and there is no benefit.

LC 142 — Linked List Cycle II · Medium

Problem. Return the node where the cycle begins, or NoneNone if there is no cycle. Do not modify the list.

Constraints. 0 <= number of nodes <= 10^40 <= number of nodes <= 10^4. Can you do it in $O(1)$ memory?

Examples. [3,2,0,-4][3,2,0,-4] with the tail linked to index 1 returns the node at index 1 · [1][1] with no cycle returns NoneNone

Editorial

Phase 1 finds a meeting point; phase 2 converts it into the cycle entrance.

Time $O(n)$ . Space $O(1)$ .

Why phase 2 works. Let LL be the distance from the head to the cycle entrance, CC the cycle length, and mm the distance from the entrance to the meeting point. When they meet, slow has travelled L + mL + m and fast 2(L + m)2(L + m), and their difference must be a whole number of laps: L + m = nCL + m = nC. So L = nC - mL = nC - m — meaning walking LL steps from the head, and LL steps forward from the meeting point, both land on the entrance. Hence stepping both pointers one at a time from those two positions makes them meet exactly there.

Being able to give that argument is the point of the problem; the code is six lines.

The test compares with isis because the problem specifies returning the node. A solution that finds the right position but constructs a new node would fail, correctly.

Follow-ups: “Prove phase 2” — the arithmetic above; the expected question. “Cycle length?” — walk from the meeting point back to itself. “With a visitedvisited set?” — $O(n)$ space, trivial, and the reason the $O(1)$ version is asked for. “Where else does this apply?” — LC 287 below, and Happy Number (LC 202), where the “list” is a function.

LC 287 — Find the Duplicate Number · Medium

Problem. An array of n + 1n + 1 integers, each in [1, n][1, n], contains exactly one repeated number. Return it without modifying the array and using only $O(1)$ extra space.

Constraints. 1 <= n <= 10^51 <= n <= 10^5, values in [1, n][1, n], exactly one value repeats (possibly many times).

Examples. [1,3,4,2,2][1,3,4,2,2] gives 22 · [3,1,3,4,2][3,1,3,4,2] gives 33 · [3,3,3,3,3][3,3,3,3,3] gives 33

Editorial

The reframing is everything: read the array as a function i -> nums[i]i -> nums[i], giving a linked structure. Since every value is in [1, n][1, n] but there are n + 1n + 1 indices, two indices must point at the same place — so the structure has a cycle, and the duplicated value is precisely the node where two arrows converge, i.e. the cycle entrance.

Then it is LC 142 applied to indices instead of nodes.

Time $O(n)$ . Space $O(1)$ , and the array is untouched — which is exactly what the constraints demand.

Why the obvious solutions are excluded: a setset is $O(n)$ space; sorting modifies the array (and is $O(n \log n)$ ); the cyclic-sort marking trick also modifies it. Those constraints exist to force this insight.

Starting at nums[0]nums[0] rather than index 00 matters: because values are at least 11, index 00 is never a target, so it cannot be inside the cycle — which makes it a valid “head” outside the loop.

[3,3,3,3,3][3,3,3,3,3] giving 33 is the many-repeats case, and [1,1][1,1] is the minimum size.

Follow-ups: “Prove there must be a cycle” — pigeonhole on n + 1n + 1 indices into nn values. “Binary search on the value range?” — also $O(1)$ space: count how many values are <= mid<= mid and compare against midmid; $O(n \log n)$ but easier to explain. “If modification were allowed?” — mark visited slots by negation, $O(n)$ . “Multiple duplicates?” — Floyd’s finds one; you would need a different approach for all.

LeetCode problem set

#	Problem	Difficulty	The twist
141	Linked List Cycle	Easy	The base template: if the pointers ever meet, there is a cycle
142	Linked List Cycle II	Medium	Once they meet, reset one pointer to the head and advance both by one — they meet at the entrance
876	Middle of the Linked List	Easy	Slow lands on the middle exactly when fast runs off the end
202	Happy Number	Easy	The ‘linked list’ is the digit-square function — same cycle detection, no nodes involved
287	Find the Duplicate Number	Medium	Treat `i -> nums[i]i -> nums[i]` as a linked list; the duplicate value is the cycle entrance

Recap

Fast and slow pointers detect cycles in $O(n)$ time and $O(1)$ space — no hash set of visited nodes required.
The same two-speed idea finds a linked list’s middle (fast finishes when slow is halfway) and, with a second phase, the cycle’s start.
The pattern isn’t limited to linked lists — any “repeatedly apply a function” sequence (Happy Number, Find the Duplicate Number) fits too.
Cue: “does this ever loop/repeat” with no room for extra memory.

Next: Merge Intervals — sorting overlapping ranges by start time and collapsing them into a minimal set.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Fast and Slow Pointers

What you’ll learn

The pattern

How it works

Worked example

Time and space complexity

When to use it

Practice — real LeetCode problems

LC 141 — Linked List Cycle · Easy

LC 142 — Linked List Cycle II · Medium

LC 287 — Find the Duplicate Number · Medium

LeetCode problem set

Recap

Was this page helpful?