Recap: Fast and Slow Pointers

Fast at twice the speed finds the middle when it stops, proves a cycle when it meets slow, and finds the cycle's start with a second walk.

Fast and slow pointers walk a list, or any sequence where each value fixes the next, at two speeds, in O(n) time and O(1) extra space. After k moves slow has gone k nodes and fast 2k, so fast stopping puts slow at the middle, and inside a cycle fast gains one node a move, so it meets slow and cannot jump over it. Each question changes only how fast moves, when the walk stops and what follows:

Four questions answered with two pointers
Question	Fast moves	Stop when	Then	Answer
Where is the middle?	Two nodes	`fast` or `fast.next` is null	Nothing	Slow's node, the second middle of an even list
Does the list loop?	Two nodes	Fast reaches null, or slow and fast meet	Nothing	A cycle when they meet, none when fast reaches null
Where does the loop start?	One node, from the meeting point	The pointers meet again	Slow first goes back to the head	The node where they meet
How long is the loop?	Not used	A pointer from the meeting point is back on it	Count the moves	The count

Compare list nodes by identity and computed values by value. The meeting point is not the start of the cycle except by chance: the second walk works because a + b, the distance slow covered, is a whole number of laps.

← → move through sections and cards