Fast & Slow Pointers

Fast & slow pointers (Floyd’s “tortoise and hare”) is a small, elegant trick that shows up in almost every linked-list question — and its power is doing cycle detection in O(1) space.

The idea

Advance slow by one node and fast by two nodes each tick:

• If the list ends (fast or fast.next becomes null), there is no cycle.
• If there is a cycle, fast keeps looping and eventually laps slow — they must land on the same node. That’s your cycle detection, in O(n) time and O(1) space (you don’t need a hash set of visited nodes).

The template

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:        # they met → cycle
            return True
    return False                # fast reached the end → no cycle

Finding the middle of a list

The same two speeds give you the middle for free: when fast reaches the end, slow is exactly at the middle (fast moves twice as far):

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow      # the middle node

Finding where the cycle starts

A classic follow-up. After slow and fast meet inside the cycle, reset one pointer to the head and advance both one step at a time — they meet at the cycle’s entrance (a neat consequence of the distance maths):

def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next; fast = fast.next.next
        if slow is fast:                 # meeting point
            p = head
            while p is not slow:
                p = p.next; slow = slow.next
            return p                      # start of the cycle
    return None

Step-by-step walkthrough

Trace Middle of the Linked List on 1 → 2 → 3 → 4 → 5 → 6 → 7. Slow moves one node per step, fast moves two. When fast reaches the end, slow has covered exactly half the distance.

Fast hits the last node after 3 steps; slow is at 4, the middle — with no length count and O(1) extra space. The same two-speed idea detects a cycle: if there is a loop, fast eventually laps slow and they land on the same node.

When to reach for it

Signals: a linked list where you need to detect a cycle, find its start, or find the middle; or any problem where following a sequence of steps might loop (the “happy number” problem applies it to digit-square sums). The key reason to prefer it over a hash set of visited nodes: O(1) space.

Pitfalls

• Null checks. fast.next.next can dereference null — always guard with while fast and fast.next.
• Even vs odd length middle. Decide whether you want the first or second middle for even-length lists, and set the loop condition accordingly.
• Reaching for a hash set. A visited-set works and is easier to reason about, but it’s O(n) space — interviewers often want the O(1) two-pointer version, so know it.

Recap

Two pointers at different speeds (slow 1, fast 2) detect a cycle when they meet, find the middle when fast reaches the end, and locate the cycle start with a little more maths — all in O(n) time, O(1) space. Signal: linked list + cycle / middle, or any sequence that might loop. The O(1) space is the whole selling point over a visited set.

Practice: 10 solved problems on fast & slow pointers → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 6 — Hash Maps & Frequency, trading memory for O(1) lookups.