Fast & Slow Pointers (Cycle Detection)

The mental model: a circular running track

Forget linked lists for a second. Two runners start at the same point on a track. Runner A (the tortoise) moves at speed 1. Runner B (the hare) moves at speed 2. Two things can happen:

• The track is finite and open-ended. The hare reaches the finish line first. The tortoise is still somewhere on the track. They never meet again.
• The track is a loop. The hare laps the tortoise. They meet somewhere on the loop.

That is the entire algorithm. Translate "runner" to "pointer" and "track" to "linked list" and you have fast/slow pointers.

Why does the hare always catch the tortoise on a loop — why can't it skip past? Because the hare is only 1 step faster than the tortoise. Each iteration the gap between them decreases by exactly 1. A gap that decreases by 1 per step will hit 0 before it can wrap around. They can't miss each other.

Why the math actually works

Here is the formal argument, kept short. Say your list has μ nodes before the cycle starts (the "tail"), and the cycle has length λ. Once both pointers enter the cycle:

• Let d = distance between fast and slow inside the cycle.
• Each step: slow moves 1, fast moves 2, so the gap shrinks by 1.
• Since d starts at some value 1 ≤ d < λ and decreases by 1 each step, it reaches 0 in at most λ − 1 steps.

Total meeting time: at most μ + λ steps. Both pointers enter the cycle by step μ (slow does, for sure). After that, at most λ more steps to close the gap. That is O(n) worst case with O(1) space — no matter the size of the list.

flowchart LR
    H["HEAD"]
    N1["node 0"]
    N2["node 1"]
    N3["node 2<br/>(cycle start μ=2)"]
    N4["node 3"]
    N5["node 4"]
    N6["node 5"]
    H --> N1 --> N2 --> N3 --> N4 --> N5 --> N6
    N6 -->|"back edge"| N3
    style N3 fill:#7c5cff,color:#fff
    style N6 fill:#22d3ee,color:#0a0a0f

The purple node is where the cycle starts (μ = 2 from head). The teal node is where the back-edge connects. Fast and slow will meet somewhere in the N3→N4→N5→N6→N3 loop.

Core operation 1: detect a cycle

The template is two lines inside a loop.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next         # +1 step
        fast = fast.next.next   # +2 steps
        if slow is fast:
            return True          # they met — cycle confirmed
    return False                 # fast fell off the end

A few things to notice:

• You check fast and fast.next — if either is None, the list is finite and you're done.
• You advance before checking equality. Both start at head; checking before moving would always return True.
• is not ==. You want pointer identity (same node object), not value equality. Two separate nodes that happen to store 5 are not the same node.

Time: O(n). Space: O(1). This is dramatically cleaner than maintaining a visited set, especially when the list is huge or when you are not allowed extra memory (embedded systems, streaming contexts).

Core operation 2: find where the cycle starts

Detecting a cycle is useful. Knowing where the cycle starts is more useful — it tells you which node was incorrectly wired.

After slow and fast meet somewhere inside the cycle, do this:

def find_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # phase 2: reset one pointer to head
            pointer = head
            while pointer is not slow:
                pointer = pointer.next
                slow = slow.next
            return slow           # cycle start node
    return None

Why does resetting one pointer to head and walking both at speed 1 land them at the cycle start?

Here is the proof. Let μ be the length of the tail (head → cycle start) and λ be the cycle length. When slow and fast meet, slow has taken some number of steps k = μ + a (it has traveled through the tail and a steps into the cycle). Fast has taken 2k steps, so fast = μ + a + b·λ for some integer b (it has gone around the cycle some number of extra times).

Since they are at the same node: 2k − k = b·λ → k = b·λ. Which means μ + a = b·λ, so μ = b·λ − a.

Now you reset pointer to head and walk both at speed 1. After μ steps, pointer is at the cycle start. Where is slow? It was at position a inside the cycle; after μ more steps it is at position a + μ = a + (b·λ − a) = b·λ ≡ 0 (mod λ) — also at the cycle start. They meet exactly at the entry point.

That is not a coincidence. It is the reason the algorithm works, and it is the thing interviewers expect you to be able to explain.

flowchart TD
    A["phase 1: hare meets tortoise inside cycle<br/>meeting point is 'a' steps past cycle start"]
    B["reset one pointer to HEAD"]
    C["advance both at speed 1"]
    D["they meet at: cycle start node"]
    A --> B --> C --> D
    style D fill:#00ff9d,color:#0a0a0f

Core operation 3: find the middle of the list

No cycle involved. You just want the middle node.

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

When fast exhausts the list, slow is at the midpoint. Because fast moves 2x as fast, when fast has traveled n nodes, slow has traveled n/2. For even-length lists, slow lands on the second of the two middle nodes (useful for most problems; adjust if you need the first).

This comes up constantly — palindrome check on a linked list, merge sort on a linked list, and a handful of DP problems modeled as lists. Internalize it as a reflex.

Worked problem 1: linked list cycle (LeetCode 141)

Classic. Given the head of a linked list, return true if there is a 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 is fast:
            return True
    return False

Nothing surprising here — this is the template. The variant is LeetCode 142 (return the node where the cycle starts), which is the two-phase Floyd above.

Worked problem 2: happy number (LeetCode 202)

This one catches people off guard because it doesn't look like a linked list problem at all. A "happy number" is one where if you repeatedly replace the number with the sum of the squares of its digits, you eventually reach 1. Unhappy numbers cycle endlessly without reaching 1.

For example, starting from 19:
1² + 9² = 82 → 8² + 2² = 68 → 6² + 8² = 100 → 1² + 0² + 0² = 1. Happy.

But starting from 4:
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4. It cycles back to 4.

This is a cycle detection problem. The function f(x) = sum of squared digits of x generates a sequence. Either it reaches 1 (which maps to itself forever: trivial cycle at 1) or it enters a loop that never includes 1. Floyd's algorithm works on any repeated-function sequence, not just linked lists.

def digit_square_sum(n: int) -> int:
    total = 0
    while n:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total

def isHappy(n: int) -> bool:
    slow = n
    fast = digit_square_sum(n)           # fast starts one step ahead
    while fast != 1 and slow != fast:
        slow = digit_square_sum(slow)
        fast = digit_square_sum(digit_square_sum(fast))
    return fast == 1

When fast == 1, you have reached the fixed point — happy number. When slow == fast at some value other than 1, you have detected the unhappy cycle. The f(x) function plays the role of node.next.

This problem is a great tell for recognizing the pattern. Anytime you see "repeatedly apply a function until it converges or cycles," that is fast/slow pointers.

Worked problem 3: find the duplicate number (LeetCode 287)

You have an array of n + 1 integers, each in the range [1, n]. Exactly one number is repeated. Find it without modifying the array and in O(1) extra space.

The trick: treat the array as a linked list. arr[i] is the "next" pointer from node i. Because every value is in [1, n] and indices are in [0, n], this defines a functional graph. Because there is a duplicate value d, two indices point to the same "next" node — which means there is a cycle, and the cycle starts at d.

def findDuplicate(nums: list[int]) -> int:
    # phase 1: find meeting point inside cycle
    slow = nums[0]
    fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # phase 2: find cycle start = duplicate value
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

This is Floyd's algorithm on the functional graph the array defines. No extra space, O(n) time. Without this insight — recognizing the array as a linked list — the only O(1)-space solutions involve sorting (which modifies the array) or arithmetic tricks that fail for duplicate counts > 2. The cycle-detection lens is the clean path.

The pattern + the tell

Here is how you recognize fast/slow pointer problems in the wild:

Signal in the problem	What it's really asking
"Does this linked list have a cycle?"	Cycle detection — Floyd phase 1
"Where does the cycle start?"	Floyd both phases
"Find the middle of a linked list"	Fast reaches end → slow is at middle
"Find the nth node from the end"	Fast goes n steps ahead first, then both advance together
"Detect infinite loop / cycle in a function sequence"	Floyd on f(x) instead of node.next
"Find duplicate in [1..n] array, O(1) space"	Array-as-linked-list + Floyd

The skeleton is always the same:

slow = fast = head   # (or starting_value for non-list problems)

# phase 1: advance at 1x and 2x speed until meeting or end
while fast and fast.next:           # termination condition varies by problem
    slow = slow.next                # or f(slow)
    fast = fast.next.next           # or f(f(fast))
    if slow is fast:
        break                       # cycle confirmed

# phase 2 (only if you need the cycle start):
slow = head
while slow is not fast:
    slow = slow.next
    fast = fast.next
return slow                         # cycle start

Everything else is filling in the blank at next / f(x).

Pitfalls

Checking equality before the first move. slow and fast both start at head. If you check slow == fast before advancing, you immediately return True on any input. Advance first, then check.

Using == instead of is. Two nodes with the same value are not the same node. ListNode(5) == ListNode(5) might be True in some implementations, but they are different objects. You want pointer identity. Always use is when comparing node references.

Wrong termination condition. You need while fast and fast.next, not just while fast. If the list has an odd number of nodes, fast.next.next will try to dereference None.next and crash if you only guard against fast is None.

Forgetting the two-phase for cycle start. Knowing that there is a cycle is not the same as knowing where it starts. Many people implement the detection but blank on the reset-to-head trick under interview pressure. Drill it separately.

Assuming "fast moves at 3x" works for cycle start. It still detects cycles, but the cycle-start proof breaks. The mathematical argument for the meeting-point relies specifically on the 2:1 speed ratio. If you use 3x, you can find the meeting point but need a different method to find the start. Stick to 2x.

When NOT to use this technique

Fast/slow pointers are specifically useful when you're walking a sequence structure and can't afford extra space. You shouldn't reach for them when:

• You have an array and can use a hash set. If memory isn't constrained and you just need to know if a value repeats, a seen = set() is clearer, faster to write, and costs the same O(n) time. The fast/slow trick on arrays (like LeetCode 287) is an intellectual exercise justified by the O(1) space constraint. Without that constraint, it's overkill.
• The sequence is random-access. If you can index into it, use two pointers converging from opposite ends — usually cleaner.
• You need more than the cycle's existence or start. Floyd tells you whether a cycle exists and where it begins. It does not tell you the cycle's length (you need an extra pass for that), and it doesn't enumerate all nodes in the cycle. If you need that information, a hash set of visited nodes is more straightforward.
• The structure is not singly-linked. If you have a doubly-linked list and can traverse backward, or a tree where you can visit parent nodes, the problem structure is different and cycle detection usually isn't the primary lens.

If you're working with an actual linked list and memory is plentiful, sometimes the honest answer is: keep the visited set, write the code that's obviously correct, and move on. The fast/slow technique earns its keep in constrained environments, functional sequences, and FAANG interviews.

Connections to other techniques

Fast/slow pointers live in the same family as two pointers, but the mechanics are different. Classic two pointers close a window from opposite ends — left and right converging toward some condition. Fast/slow is asymmetric: both run in the same direction, and the speed gap is the tool. Think of two-pointer as "squeeze" and fast/slow as "catch."

The underlying reasoning leans on recursion intuition: you are thinking about repeated function application — apply next once versus twice — and asking what happens at convergence. The same "what is the fixed point of this iteration?" thinking that makes recursion click will make Floyd's proof feel natural instead of magical.

If this technique unlocked something, the natural next problems to hit are: reorder list (uses find-middle + reverse), palindrome linked list (find-middle, reverse second half, compare), and any variant of the "kth from end" where fast goes k steps ahead first.

The linked list visualizer above is the right mental anchor. You are always chasing a node you cannot index into — the only tool you have is next. Two speeds, one elegant guarantee.