The Tortoise, the Hare, and the Cyclical Linked List | Hacker News Reader

The Tortoise, the Hare, and the Cyclical Linked List

medium.com

40 pointsrbanffy25 comments

This is a cool little algorithm. I've heard about it first in the context of "nightmarish interview questions" though, where a programmer was meant to derive the technique from thin air :)

Though not as elegant and concise you can get a similar result by dropping a single marker at log number of steps.

Yes it is routinely used as a way to humiliate candidates, because it's a perfect brain teaser: Devilishly simple but difficult to conjure unless you've seen it before - "Why couldn't I think of that???" Most undergrad CS curriculums won't cover it.

https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoi...

> Most undergrad CS curriculums won't cover it.

The serious ones do. At least, I found it to be commonly known.

Heh, I recall that it’s in an early chapter of the original coding interview prep book.

Another one is: you have a list of numbers, more than half of them are the same number, and you have to find it.

Ex: 1 2 3 1 1 3 1 => 1

Hints

1- It can be done in one pass, linear time, constant space

2- It doesn't have to be numbers

3- The algorithm it is literally just 2 statements in a loop

Are you allowed to modify the list?

Edit: I think I figured it out!

Features in this video: https://www.youtube.com/watch?v=pKO9UjSeLew

According to the solution in the video, the problem upthread was stated incorrectly. There's an additional constraint that only integers in the interval [1, N], where N is the size of the array, are permitted; or at least where the numbers can be trivially mapped to that interval (e.g. subtraction of an offset).

The problem upthread was stated correctly. The video shows the solution for a similar but different problem.

Ah, right. The critical constraint upthread seems to be "more than half of them are the same".

As a semi off-topic aside, the title of this post is genius!

It serves both the job of making those curious who are not in the know (and hopefully get their clicks), while also telling the rest exactly what it's about (and save our time).

Haven't gone through the proof closely, but I suspect this would work for any prime for the tortoise, not just 2 (though 2 is probably optimal in actual implementation). This is the most I've used my discrete math degree in my 2.5 years post undergrad.

Well you want kx+b = x (mod m) to have a solution for all b and m (here b depends on how much earlier the hare enters the cycle). This means you'll need to have k-1 comprime to m for all m>0. Pretty sure k-1 = 1 is the only solution.

As a counter example where both k and k-1 are prime consider k=3. Then:

3 x + b = x (mod 2)

will fail to have a solution for odd b.

> Well you want kx+b = x (mod m) to have a solution for all b and m

I prefer to think about this another way.

I'm also confused by your parent's comment "I suspect this would work for any prime for the tortoise, not just 2". In the post, 2 is the speed of the hare, and the tortoise's speed is 1.

Anyway, what you want is for the hare to meet the tortoise. In the general case, tortoise and hare both have arbitrary speeds t and h and enter the cycle at random positions.

The cycle is m nodes long. What you need is for (h - t), the amount by which the hare catches up to the tortoise, to be coprime to m. Since m could be anything, the only solution is h - t = 1. But you could have a hare going 6 nodes per timestep and a tortoise going 5.

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; the hare passing the tortoise is sufficient evidence to detect a cycle.

This change adds a performance penalty with the extra equality checks, but can reduce the total number of steps in certain contexts (e.g. lists with long cycles that appear at an early node can benefit from a much faster hare).

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

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.

> By now you may be wondering why we do not simply use a set, and return fast if we encounter a node already in the set. Or, indeed, to solve what we’re building towards, we could just return the first value which is already in the set. (...)

> However, as I mentioned, this solution is spatially inefficient,

Typically you'd need to store N pointers, and the list would be of size N(size_of(pointer) + size_of(node)) - which would normally be much larger than the pointers? (otherwise use an array, perhaps?)

What are some real world cases where long linked list of very light nodes are best checked for cycles with this algorithm?

Perhaps you don't have the entire linked list in memory, but are instead requesting individual nodes from a server.

You might have an abstract function f which takes and returns an integer, and you want to figure out if this function has “cycles”, eg if ffffff(n) = fff(n) etc. The numbers used might be enormous, and so trying to store them all is a non-starter.

Indeed, there are quite a few application in cryptography, where one has to search trough a huge space. Wikipedia actually listens a few: https://en.wikipedia.org/wiki/Cycle_detection#Applications

Obligatory link: Hexing the technical interview [1]

[1] https://aphyr.com/posts/341-hexing-the-technical-interview

Oh... This is wonderful.

"The reason is space complexity. You can't store every node in a set".

Jokes on you, I've got 128 gigs of heap.

Reply on news.ycombinator.com