| 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. |