News for hackers. Stuff that matters.
Re:Linked List Problems (2002) [pdf] by simooooo on Saturday November 25, 2017 @03:03PM (#15777691)
"It is easy to see that they will eventually meet on the cycle. Once that happens, it is easy to count the cycle length."

Is that so?

Re:Linked List Problems (2002) [pdf] by microtherion on Sunday November 26, 2017 @04:58AM (#15780206)
The second part of this confused me as well, because the algorithm only detects the existence of the cycle, not its length. However, once you know a node in the cycle (which this algorithm will provide), you simply go around the cycle once more and you have the length.
Re:Linked List Problems (2002) [pdf] by Spivak on Sunday November 26, 2017 @01:33PM (#15782259)
More specifically you stop moving the hare and send the tortoise around again until it meets the hare counting your steps along the way.