87. Why does Floyd's algorithm use steps of 1 and 2? Would steps of 1 and 3, or 2 and 3, also work?
HardLinked lists
Show model answer
With speeds 1 and 2, the relative speed inside the cycle is 1, so the fast pointer closes the gap by exactly one node per step and cannot jump over the slow pointer. They are guaranteed to meet within one lap of the slow pointer after it enters the cycle, and the μ + k multiple-of-λ argument for finding the start relies on the 2:1 ratio.
With other speeds the relative speed d may share a factor with the cycle length λ. For example, with speeds 1 and 3 (d = 2) and an even λ, the gap may always stay odd and never reach 0, so the pointers can circle forever. Detection is still guaranteed if you also vary the start, or use Brent's algorithm, but 1 and 2 is the simplest choice with an unconditional guarantee and the fewest pointer moves.