Algorithms / Fast Slow Pointers
Least You Need to Know: Fast/Slow Pointers, Middle Nodes, and Cycle Entry
Fast and slow pointers turn repeated traversal into relative-motion reasoning. The same idea explains finding middle nodes, detecting linked-list cycles, and locating the entry point after a cycle is found.
Least you need to know
- If a fast pointer moves twice as quickly as a slow pointer, their relative speed is one step per round.
- In an acyclic list, the fast pointer eventually reaches
null. - In a cyclic list, fast and slow pointers must eventually meet inside the cycle.
- After a meeting, resetting one pointer to the head and moving both one step at a time finds the cycle entry.
- The same fast/slow setup also finds middle nodes without counting the list first.
Key notation
- slow — pointer moving one step per round
- fast — pointer moving two steps per round
- cycle entry — first node on the loop reached from the head
Worked example
- Move
slowby one node andfastby two nodes. - If
fasthitsnull, the list ends and there is no cycle. - If they meet, a cycle exists.
- Reset one pointer to the head; moving both one step per round makes them meet again at the cycle entry.
Common mistakes
- Students often think a meeting point is automatically the cycle entry.
- Students often forget to guard
fastandfast.nextbefore advancing by two. - Students often miss that middle-node problems are the same relative-speed pattern without cycles.
How to recognize it
- The structure is a linked list or repeated-next-pointer chain.
- The prompt asks for a middle node, cycle existence, or cycle start.
- Relative speed is easier than explicit length counting.
Next recommended lesson
Continue through this topic with Least You Need to Know: Fenwick Point Updates, Frequencies, and Order Statistics.
Least You Need to Know: Fenwick Point Updates, Frequencies, and Order StatisticsRelated lessons
Keep going with nearby lessons in the same topic.