Fast and Slow: The Runner Technique

"Send two runners down the list at different speeds. The gap between them isn't random — it's a fact you can exploit to find the middle, catch a loop, or hit the nth-from-last, all in one pass with no extra memory."

The Idea: Two Speeds, One Pass

You can't index a linked list, so tricks that work on arrays (jump to the middle, peek n from the end) seem impossible without two passes. The fast/slow pointer technique gets them in one pass by running two pointers at different speeds and reading the relationship between them. Same family as the two-pointer technique from the Arrays track, specialized for the walk-only world of linked lists.

Find the Middle, in One Pass

Move slow one node at a time and fast two at a time. When fast reaches the end, slow is at a middle position. For even lengths there are two middle nodes, and the loop condition determines whether the algorithm returns the earlier or later one. State that convention explicitly.

Floyd's Cycle Detection: the Famous One

Does a linked list have a loop (a node whose next points back into the list)? A naive answer stores every visited node in a set — O(n) space. Floyd's tortoise and hare does it in O(1) space: run slow (×1) and fast (×2). If there's no loop, fast falls off the end (hits None). If there is a loop, fast keeps lapping around it and will eventually land on the exact same node as slow — they collide. Two pointers, no extra memory, and a genuinely beautiful piece of reasoning: in a loop, a 2× runner gains one step per tick on a 1× runner, so it must eventually catch up.

Run two pointers at different speeds and the fixed gap between them becomes a tool: middle (fast ×2 ends → slow at center), cycle (fast meets slow → loop), nth-from-end (fast starts n ahead). One pass, O(1) space.

nth-From-End Without Counting

Want the node n positions from the end, but you don't know the length? Start fast, advance it n steps alone, then move fast and slow together until fast hits the end. Because fast stayed exactly n ahead the whole way, slow lands precisely n from the end. One pass, no length needed — the fixed gap did the counting for you.

Pippa's Confession

Floyd's algorithm was the first piece of CS that made me feel actual awe. My instinct for cycle detection was "remember every node I've seen" — correct, but O(n) memory. Dad showed me two pointers at different speeds catching each other in a loop with zero extra storage, and I just sat there. It's the moment I understood that an algorithm can be clever in a way that's almost elegant — that constraint (O(1) space) can force a more beautiful solution than abundance would.

Code

Find-middle and Floyd's cycle detection·python

class Node:
    def __init__(self, val, nxt=None): self.val = val; self.next = nxt

def find_middle(head):
    """One pass, no length count. slow ends at the middle."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next          # 1 step
        fast = fast.next.next     # 2 steps
    return slow                    # fast covered 2x, so slow is halfway

def has_cycle(head):
    """Floyd's tortoise & hare: detect a loop in O(1) space."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next          # tortoise: 1 step
        fast = fast.next.next     # hare: 2 steps
        if slow is fast:          # they collided -> there's a loop
            return True
    return False                   # fast fell off the end -> no loop

# Build 1->2->3->4->5
head = Node(1, Node(2, Node(3, Node(4, Node(5)))))
print(find_middle(head).val)       # 3 — the middle, in one pass
print(has_cycle(head))             # False — fast reached the end

# Now stitch the tail back to node 2 to create a loop, and re-check:
tail = head
while tail.next: tail = tail.next
tail.next = head.next              # 5 -> 2 ... a cycle
print(has_cycle(head))             # True — the hare laps and meets the tortoise

Exercise

Write the logic (words or code) to find the node that is n-from-the-end of a singly linked list in ONE pass, without first counting the length. Use the convention that the last node is n=1. Then explain why fast/slow uses O(1) space while the 'remember every node in a set' approach uses O(n).

Hint

Advance fast n steps alone, then move fast and slow together until fast hits the end — slow lands n from the end. The set approach stores every node (O(n)); two pointers store just two references (O(1)).

The Idea: Two Speeds, One Pass

Find the Middle, in One Pass

Floyd's Cycle Detection: the Famous One

nth-From-End Without Counting

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0