3 ms·
It includes the cycle detection in a linked list problem, and even has an illustration of the classic algorithm of Floyd using the tortoise and hare. It's kind
by tzs 8y ago
It includes the cycle detection in a linked list problem, and even has an illustration of the classic algorithm of Floyd using the tortoise and hare. It's kind of fun and interesting to look at what is actually required for that algorithm to work.
It's almost always presented as having the tortoise and the hare start on the same node, with the tortoise advancing one node per iteration and the hare advancing two nodes per iteration. Let's call this a (1,2) stepping version.
That suggests the first question to explore: for what positive integers n, m does an (n, m) stepping always work, when the tortoise and hare start from the same node?
A lot of people from what I've seen think that n and m have to be relatively prime, but that is not correct.
The surprising answer is that an (n, m) stepping works for any positive n and m as long as n != m.
This is surprising, because you might expect that if you were using something like a (2, 4) stepping, and the cycle length was a multiple of 2, you could get the tortoise and hare stuck in non-intersecting loops. E.g., if the cycle length is 8 and we number the nodes in the cycle 0, 1, ..., 7, and the nodes before we reach the cycle are -1, -2, -3, ..., couldn't we end up where the tortoise gets stuck in looping over 0, 2, 4, 6, and the hare gets stuck out of phase with the hare looping over 1, 5?
It turns out that there is no way for the hare to enter the loop at 1 without the tortoise also entering the loop at 1, which puts the tortoise on the 1, 3, 5, 7, and it will meet the hare. This is a consequence of the tortoise and hare starting from the same node.
That suggests the second question to explore: what is required for an (n, m) stepping to guarantee it works regardless of the starting nodes of the tortoise and hare?
The answer there is the difference in speed, m-n, has to be relatively prime to the cycle length.
Note that (1, 2) is a stepping that works universally. If the tortoise and hare start at the same node, it works because 1 != 2. If they start on different nodes, it works because 2-1 = 1, and 1 is relatively prime to every possible cycle size.
But (1,2) is not the only stepping that works universally. (n, n+1) works for the same reason.
That suggests a third question to explore: are there circumstances where it is better to use an (n, n+1) stepping with n > 1 than to use (1, 2)?
- lordnacho 8y agoThe linked list cycle problem was an open question for many years in the mid 20th century. You may have discovered why: it's not actually as easy as it seems when you know the answer. There's a blog post about this somewhere, how it's not actually a great question to ask.