[thaumasiotes]

> If you check every node that the hare enters, you don't need the relative speed to be coprime to the cycle-length. This eliminates the need for the hare and tortoise to finish a round on the same node

> This change adds a performance penalty with the extra equality checks, but can reduce the total number of steps in certain contexts

The post seems to think that most of the value in this approach comes from the fact that it's easy to identify the beginning of the cycle after you've identified that the cycle exists. The method relies on the tortoise and hare finishing a round on the same node. Does that generalize to the case where the hare just passes the tortoise at some point?

[bombastry]

I wasn't thinking about that when I commented, but you're absolutely right. I definitely missed the point.

I don't think there is any way to generalize the algorithm in the article to work on the method I described. However I was able to find an alternate algorithm to find the initial node of the cycle. It also has linear time complexity and constant storage, but it requires that the pointers in each node be mutable. It is also worse than Floyd's algorithm in almost every way. The algebra gets a little annoying, so I've just provided the informal algorithm below.

0) Find the meeting point as described above.

1) Find the cycle length.

2) Find the distance to the meeting point k+x (where k is the length of the linear portion and x is the number of nodes from the start of the cycle to the meeting point).

   2a) If the hare speed is double the tortoise speed and the tortoise speed is less than the cycle length, this can be found directly.

   2b) Otherwise, we can send a probe from the head until it reaches the meeting point.

This unfortunately this isn't enough information to find the initial node of the cycle, so more drastic measures are needed.

3) Reverse all of the nodes of the cycle (We can actually do this during step 1 if we want to be more efficient, although some care needs to be taken (e.g. that step 2b is performed first).)

4) Send a probe from the head and count the steps until it reaches the meeting point node. This will have gone k + m - x steps.

5) Now we use some algebra to get x in terms of k and known values. We can substitute this into our equation that gives a known value for k+x (from step 3) to find k.

6) Reverse all the nodes of the cycle so they are back to how they originated.

7) Advance k times to reach the first node of the cycle; return this node.

The additional steps have a linear order complexity with respect to the number of nodes of the linked list. And like the OP algorithm, only a constant amount of storage is necessary, although reversing the list will require a couple more pointers to nodes. I'm not sure if there are many cases where this would perform better, but if they do exist they seem like they would be extremely rare.