Fast and Slow Pointers Example: Finding Where the Cycle Starts

After the pointers meet, one goes back to the head and both move one node at a time: they meet again at the first node of the cycle.

A second walk after the meeting finds the first node of the cycle: move one pointer back to the head, leave the other at the meeting point, and advance both one node at a time until they meet. The route A B C D E F, with F linking back to C, shows both phases. The first phase is the cycle check, and the pointers meet on E.

Phase 1: slow and fast until they meet

InputA → B → C → D → E → F → C

Start: both on A
1. Aslowfast
2. B
3. C
4. D
5. E
6. F
Both start on A
Move 1: slow B, fast C
1. A
2. Bslow
3. Cfast
4. D
5. E
6. F
Slow one step, fast two
Move 2: slow C, fast E
1. A
2. B
3. Cslow
4. D
5. Efast
6. F
Both are now inside the loop C D E F
Move 3: slow D, fast C
1. A
2. B
3. Cfast
4. Dslow
5. E
6. F
Fast wraps from F back to C
Move 4: slow E, fast E
1. A
2. B
3. C
4. D
5. Eslowfast
6. F
They meet on E

ResultThey meet on E, which is inside the cycle but is not its first node.

In the second phase slow goes back to A and fast stays on E, and now both move one node a move.

Phase 2: one pointer from the head, one from the meeting point, both at one node a move

InputA → B → C → D → E → F → C

Phase 2: slow back on A, fast on E
1. Aslow
2. B
3. C
4. D
5. Efast
6. F
Slow restarts at the head, fast stays where they met
Step 1: slow B, fast F
1. A
2. Bslow
3. C
4. D
5. E
6. Ffast
Both move one node: slow on B, fast on F
Step 2: slow C, fast C
1. A
2. B
3. Cslowfast
4. D
5. E
6. F
Fast goes from F to C and slow from B to C: they meet on the first node of the cycle

ResultThe cycle starts at C.

It works because of what the meeting says about distances. The table names them for this list.

The distances behind the second phase, on this list
Symbol	Meaning	Value on this list
a	Nodes from the head to the first node of the cycle	2: A and B
b	Nodes from the first node of the cycle to the meeting point	2: C to E
L	Nodes in the cycle	4: C D E F
a + b	Nodes slow walked before the meeting	4
2(a + b)	Nodes fast walked before the meeting	8

Fast walked a + b more nodes than slow and ended on the same node, so its extra a + b nodes are whole laps of the cycle: a + b is a multiple of L, here 4 = 1 × 4. A pointer at the meeting point is b nodes into the cycle, so a more nodes take it to b + a, a whole number of laps, which is the first node of the cycle. A pointer from the head reaches that node after the same a moves, so they meet there: on this list after a = 2 moves. Walking once round from the meeting point and counting until it comes back gives the cycle's length, 4 here. Both phases are O(n) time and O(1) extra space.

← → move through sections and cards