Pattern 3: Slow and fast pointers
Two pointers walking through the list at different speeds reveal surprising things: the middle of the list in a single pass, and whether a cycle exists — without using any extra memory.
Try it first: Middle of the Linked List
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
Return the middle node of a linked list (from it to the end). If there are two middle nodes, return the second.
Example: 1 → 2 → 3 → 4 → 5 → middle is 3 (returns 3 → 4 → 5). 1 → 2 → 3 → 4 → 5 → 6 → returns 4 → 5 → 6.
Did you try? You can count the size and walk halfway — two passes. The theory below does it in a single pass, with an idea that pays off far more than just finding the middle.
The theory: different speeds
The idea (also called "tortoise and hare"): two pointers start at the head, but
fast moves two nodes at a time while slow moves one.
slow: +1 per step
fast: +2 per step
Since fast covers twice the distance, when it reaches the end, slow has
covered exactly half — that is, it is at the middle. One pass, without
counting anything first:
(With an even number of nodes, this code returns the second of the two middle nodes — adjust the loop condition depending on whether the prompt asks for the first or the second.)
Why is it O(n) time and O(1) space?
fast traverses the list once (in steps of 2), so the loop runs ~n/2 times,
each one O(1) → O(n) time. Two pointers, no extra structure → O(1)
space. The "count and walk halfway" alternative is O(n) too, but makes
two passes.
The big trick: cycle detection (Floyd)
What if the list has a cycle (some next points back to an earlier node)? A
while curr loop would run forever. How do you detect it without marking nodes
or using a set (which would cost O(n) memory)?
Floyd's insight: release the tortoise (slow, +1) and the hare (fast, +2)
onto the track. If the track is straight (no cycle), the hare reaches the
end (None) and that's that. If the track is circular, the hare keeps going
around and, sooner or later, catches up to the tortoise from behind —
because at each step the distance between them shrinks by 1. If fast == slow
at some point, there is a cycle.
Why Floyd works (and is O(1) space)
If there is a cycle, once both are inside it, the hare gets 1 position
closer to the tortoise at every step (it moves 2, the tortoise moves 1). The
distance only shrinks, so within at most "cycle length" steps they meet. If
there is no cycle, the hare reaches None and the loop ends. It costs
O(n) time and O(1) space — the obvious alternative (storing seen nodes
in a set) is also O(n) time, but spends O(n) memory. Floyd spends none.
Where slow/fast shows up
- Middle of the list (and from there: splitting the list in half — the basis of merge sort on lists and of reorder).
- Cycle detection and, with one extra step, finding where the cycle begins.
- N-th from the end (the fixed gap from the previous lesson is a cousin of this pattern).
🧠 Quick-check quiz
0/41. Why, when fast (step 2) reaches the end, is slow (step 1) at the middle?
2. In Floyd's cycle detection, why do slow and fast end up meeting if there is a cycle?
3. Why is Floyd preferable to storing the visited nodes in a set?
4. How does detecting a cycle in a 'while fast and fast.next' loop guarantee termination when there is NO cycle?
Summary
- Slow/fast: fast moves 2, slow moves 1 → slow stops at the middle when fast runs out. One pass, O(n)/O(1).
- Floyd (cycle): if there is a cycle, the hare catches the tortoise; if not, the hare finds the end. O(n)/O(1), no set.
- The basis for splitting the list, finding the start of the cycle, and "n-th from the end".
Next lesson: merging two sorted lists — merge.