4 ms·
"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?
by simooooo 9y ago
"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?
- microtherion 9y agoThe 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.
- Spivak 9y agoMore specifically you stop moving the hare and send the tortoise around again until it meets the hare counting your steps along the way.