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.