Complexity of Floyd's Cycle Detection

Two pointers move at different speeds through the sequence without any extra data structure.

Bound the number of steps before the fast pointer either exits or meets the slow pointer.

1. 1. Describe the two-pointer approach

   A slow pointer advances one step at a time while a fast pointer advances two steps; if there is a cycle, the fast pointer eventually meets the slow pointer, using only two pointer variables.

2. 2. Bound the complexity

   The fast pointer can traverse the whole structure at most a constant number of times before meeting the slow pointer (if a cycle exists) or reaching the end, giving $O(n)$ time, while only two extra pointers are stored, giving $O(1)$ auxiliary space.

Answer: O(n) time and O(1) auxiliary space.