Does a Delivery Route Loop Back? From a Visited Set to Two Speeds

Remembering every stop visited costs memory for the whole route; two pointers at different speeds must meet inside a loop and never meet without one.

Two pointers at different speeds prove whether a linked list loops back on itself, in O(1) extra memory, because they meet inside a loop and never meet without one. A cycle is a node whose next points back to an earlier node, so walking the list never reaches its end. A delivery route is stored as a list of stops, A B C D E F, each naming the next, and a mistake in the data may have sent F back to C. Following the route by hand would go round C D E F for ever.

The brute force remembers. Walk the route and put each stop in a set; a stop already in the set proves a cycle, and reaching the end proves none. That is O(n) time for n stops and O(n) extra space, because the set holds every stop. Here the cost worth removing is the memory, not the time: the walk is already linear.

Two speeds remove the set. Slow moves one stop a move and fast moves two. Without a cycle, fast reaches the end and the answer is no. With one, both pointers end up inside the loop, and from then on fast gains exactly one stop on slow every move, so the gap between them shrinks by one each time and reaches 0: fast cannot jump over slow. The meeting proves the cycle, and fast reaching null proves there is none.

A visited set against two speeds

Visited setO(n) time, O(n) space

Record every stop; a stop seen twice is a cycle. The set grows with the route.

Two speedsO(n) time, O(1) space

Move slow by one and fast by two; a meeting is a cycle, and fast reaching null is none. Two references, whatever the length.

The trace runs the two speeds on the route, with the link from F back to C written in the input.

Slow and fast on A B C D E F, with F linking back to C

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 on B, fast two ahead on C
Move 2: slow C, fast E
1. A
2. B
3. Cslow
4. D
5. Efast
6. F
Fast is on E, two ahead of slow
Move 3: slow D, fast C
1. A
2. B
3. Cfast
4. Dslow
5. E
6. F
Fast goes from E through F back to C, one behind slow inside the loop
Move 4: slow E, fast E
1. A
2. B
3. C
4. D
5. Eslowfast
6. F
Fast gains one more stop and lands on slow: they meet on E

ResultThe pointers meet on E after four moves, so the route loops.

Once both were inside the loop, after move 2, fast was two stops behind slow going round, then one, then none. Inside a loop of L stops slow is caught within one lap, so the walk is O(n) time, and the two references are O(1) space. The meeting says that a cycle exists; it does not say where the cycle starts, which takes a second walk from the meeting point.

← → move through sections and cards