Fast and slow pointers

Many linked-list problems fall to a single trick: walk two pointers through the list at different speeds. The slow pointer takes one step at a time; the fast pointer takes two. What the gap between them reveals is surprisingly powerful.

Finding the middle

Advance slow by one and fast by two each step. By the time fast falls off the end, slow sits at the middle — it has covered exactly half the distance.

function middle(head):
    slow, fast = head, head
    while fast exists and fast.next exists:
        slow = slow.next
        fast = fast.next.next
    return slow            // middle node, in one pass

One pass, O(n) time, O(1) extra space — no length count, no second traversal.

Detecting a cycle: Floyd's tortoise and hare

A linked list might loop back on itself instead of ending in nil. How do you detect that without marking nodes or using a hash set?

Floyd's tortoise-and-hare algorithm reuses the same fast/slow idea. Move slow one step and fast two steps. If the list ends, fast reaches nil — no cycle. But if there is a cycle, the fast pointer keeps looping and eventually laps the slow one, so the two meet at the same node — proof of a cycle.

function hasCycle(head):
    slow, fast = head, head
    while fast exists and fast.next exists:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return true     // hare lapped the tortoise -> cycle
    return false            // hare ran off the end -> no cycle

Why must they meet inside a loop? Once both pointers are in the cycle, the fast pointer gains one node on the slow pointer every step, so the gap shrinks by one each time until it hits zero. It's O(n) time and O(1) space — no extra memory at all.

Keep this pattern in your back pocket: two speeds, one list. The problems ahead use it to find middles, detect cycles, and more.