Fast & Slow Pointers

No. 15 · SVG · Tortoise and harecycle detection · middle of a list · Floyd's algorithm

Drag across the track. Click it, then use ← → to step and Space to play.

Two pointers walk the same linked list at different speeds: slow moves one node per turn, fast moves two. If there is a cycle, fast eventually laps slow and they land on the same node; if there isn't, fast reaches the end, and at that moment slow is exactly halfway. No visited set, no length count: O(n) time and O(1) space.

FIG. 15 · The list drawn on the board from page 6, one-way grooves pointing to next. The black marble S is slow, the red marble F is fast; their gates are ringed in the same colours, and a gate turns solid red when both stand on it. The grooves just travelled light up. Callout: A head.

Step 1 / 1
READY
Slow (1 step)
Fast (2 steps)
Extra space
Result
Codehas_cycle
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Examples

Floyd · LeetCode 142

Not just "is there a cycle" but "where does it start". After the pointers meet, move one back to the head and walk both one step at a time; they meet again exactly at the start of the cycle. Answer: node 4.

O(n) timeO(1) spacetwo walks, each at most a tail plus a lap
Floyd on an array · LeetCode 287

nums = [1, 3, 4, 2, 2]. Read index i as a node pointing to nums[i]. The repeated value has two arrows into it, so following the arrows must loop, and the loop's entrance is the duplicate. Answer: 2, without modifying the array or using extra memory. Trigger: "find the duplicate number".

O(n) timeO(1) spaceno set, no sorting, array untouched

Time and space

ApproachTimeSpaceWhy
Fast and slow pointersO(n)O(1)Once both are on the loop, the gap closes by one node per turn, so they meet within one lap.
Visited set (page 9)O(n)O(n)Remember every node; the first repeat is the cycle. Simpler, but costs memory.
Middle by countingO(n)O(1)Two passes (count, then walk n/2). Fast and slow do it in one.

Why must they meet?

Once both pointers are inside the loop, look at the gap from slow forward to fast. Each turn slow adds 1 and fast adds 2, so the gap shrinks by exactly 1. A gap that shrinks by 1 each turn hits 0; it can never jump over it. That's also why fast moves 2 and not 3: with 3 it could skip past slow.

Why does phase 2 find the start?

Say the tail before the loop has length a and they met b steps into the loop of length c. Slow walked a + b, fast walked twice that, and the extra a + b is a whole number of laps. So a ≡ c − b (mod c): walking a more steps from the meeting point lands on the loop's start, exactly where a pointer from the head arrives after a steps.

Trigger words: when the problem wants fast and slow pointers

Linked lists

  • linked list cycle
  • middle of the list

Two speeds on one list, no extra memory.

Hidden lists

  • find the duplicate number
  • happy number

Any "next" function (i → nums[i], n → sum of digit squares) forms a list you can race on.

Template

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

def middle(head):                  # second middle if even length
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow