Fast & Slow Pointers#
Also known as: Floyd's Cycle Detection, Tortoise and Hare, Runner Technique
Two pointers move through the structure at different speeds. If there's a loop, the fast one eventually laps the slow one and they collide. If there isn't, the fast one falls off the end. The same trick, stopped halfway, finds the middle of a list in one pass.
Before you start#
- Comfortable with linked list traversal in your language — following .next references.
What 'solved properly' looks like
Target: O(n) time, O(1) space. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea#
You move one pointer one step at a time and another two steps at a time. In a cycle, the fast pointer will eventually lap the slow one — they meet, and you know there's a loop. Without a cycle, the fast pointer reaches the end first. The same mechanism, stopped at the halfway point, finds the middle element of a list in a single pass without counting length first.
Why it matters: It's the answer whenever "just use a hash set" is available but the problem demands O(1) space. And it generalises beyond linked lists to any sequence where each value determines the next one — like the numbers in Happy Number or Find the Duplicate Number.
When to reach for it#
Reach for it for linked-list cycles, finding the middle of a list, or any problem involving a sequence where each value points to the next — that's still a linked list, just not one you can draw.
When not to use it
If extra space is allowed, a hash set is simpler and clearer. This pattern earns its complexity only when O(1) space is required — don't reach for cleverness you don't need. Watch the even/odd-length case when finding the middle: which of the two middle nodes you land on depends on your loop condition, and problems care about which one they want.
Practice set#
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Middle of the Linked List | LeetCode | Easy | 15 mins | teaching |
| 2 | Linked List Cycle | LeetCode | Easy | 15 mins | teaching |
| 3 | Happy Number | LeetCode | Easy | 20 mins | consolidation |
| 4 | Remove Nth Node From End of List | LeetCode | Medium | 20 mins | consolidation |
| 5 | Find the Duplicate Number | LeetCode | Medium | 35 mins | challenge |
Already know this? Test out.
If you can solve Find the Duplicate Number cleanly in one sitting — recognising it as a linked-list cycle problem and implementing Floyd's algorithm — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.