Another way to think about it, notice that the distance between the two pointers increase by 1
after every iteration (one travels by 2
, one travels by 1
, so the distance increases). The distance is always going to be original distance
+ distance increase each iteration
(which is 1, 2, 3, ..). Because they are moving in a fixed-length cycle, they'll eventually meet.
The space complexity of the algorithm is O(1)
.