AlgoScope

Detect Cycle

If fast ever lands on slow, the list loops. On a straight list fast just runs out.

Linked list algorithms, algorithm, intermediateAlso called Floyd's tortoise and hare
Slow is at 2 and fast at 3.123456headslowfast
Slow is at 2 and fast at 3.123456headslowfast

Fast and Slow Pointers: A list that loops

Decision, step 2 of 6

Step 1: slow to 2, fast to 3.

How fast and slow pointers works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

Fast and Slow Pointers covers these too, in the same run.