News for hackers. Stuff that matters.
Re:Linked List Problems (2002) [pdf] by RomanPushkin on Saturday November 25, 2017 @02:47AM (#15774916)
3 will also work. People pick 2 intuitively, and it minimizes the overall runtime of the algorithm.

(google "Proof of Floyd's Cycle Chasing" for details)

Re:Linked List Problems (2002) [pdf] by tzs on Saturday November 25, 2017 @05:40AM (#15775400)
Another advantage of 2 is that it works even if the two pointers do not start on the same element.
Re:Linked List Problems (2002) [pdf] by Spivak on Sunday November 26, 2017 @01:35PM (#15782271)
It's not specifically 2, any two speeds that are coprime will have the same property.
Re:Linked List Problems (2002) [pdf] by tzs on Tuesday November 28, 2017 @02:41AM (#15795207)
Counterexample: loop of 8 nodes, numbered 0, 1, ..., 7.

Start with one pointer at node 0, moving with speed 5. Start the second pointer at node 1, with speed 3 which is coprime to 5, the speed of the first pointer.

The pointer positions at each step are:

  0 5 2 7 4 1 6 3 repeat
  1 4 7 2 5 0 3 6 repeat
The condition we need in order to guarantee it works regardless of where the two pointers start is that the difference between the speeds is coprime to the cycle length.