How does finding a cycle start node in a cycle linked list work?

Question

I understand that Tortoise and Hare's meeting concludes the existence of a loop, but how does moving tortoise to the beginning of linked list while keeping the hare at the meeting place, followed by moving both one step at a time make them meet at the starting point of the cycle?

Solution 1

This is Floyd's algorithm for cycle detection. You are asking about the second phase of the algorithm -- once you've found a node that's part of a cycle, how does one find the start of the cycle?

In the first part of Floyd's algorithm, the hare moves two steps for every step of the tortoise. If the tortoise and hare ever meet, there is a cycle, and the meeting point is part of the cycle, but not necessarily the first node in the cycle.

When the tortoise and hare meet, we have found the smallest i (the number of steps taken by the tortoise) such that X_i = X_2i. Let mu represent the number of steps to get from X₀ to the start of the cycle, and let lambda represent the length of the cycle. Then i = mu + alambda, and 2i = mu + blambda, where a and b are integers denoting how many times the tortoise and hare went around the cycle. Subtracting the first equation from the second gives i = (b-a)*lambda, so i is an integer multiple of lambda. Therefore, X_{i + mu} = X_mu. X_i represents the meeting point of the tortoise and hare. If you move the tortoise back to the starting node X₀, and let the tortoise and hare continue at the same speed, after mu additional steps the tortoise will have reached X_mu, and the hare will have reached X_{i + mu} = X_mu, so the second meeting point denotes the start of the cycle.

Solution 2

Let me try to clarify the cycle detection algorithm that is provided at Wikipedia - Tortoise_and_hare in my own words.

How it works

Let's have a tortoise and a hare (name of the pointers) pointing to the beginning of the list with a cycle, as in the diagram above.

Let's hypothesize that if we move the tortoise 1 step at a time, and the hare 2 steps at a time, they will eventually meet at a point. Let's show that first of all this hypothesis is true.

The figure illustrates a list with a cycle. The cycle has a length of n and we are initially m steps away from the cycle. Also, let's say that the meeting point is k steps away from the cycle beginning and tortoise and hare meets when tortoise has taken i total steps. (Hare would have taken 2i total steps by then.).

The following 2 conditions must hold:

1) i = m + p * n + k

2) 2i = m + q * n + k

The first one says that the tortoise moves i steps and in these i steps, it first gets to the cycle. Then it goes through the cycle p times for some positive number p. Finally, it goes over k more nodes until it meets hare.

A similar thing is true for hare. It moves 2i steps and in these 2i steps it first gets to the cycle. Then it goes through the cycle q times for some positive number q. Finally, it goes over k more nodes until it meets the tortoise.

As the hare travels with double the speed of the tortoise, and time is constant for both when they reach the meeting point.

So by using simple speed, time and distance relation,

2 ( m + p * n + k ) = m + q * n + k

=> 2m + 2pn + 2k = m + nq + k 

=>  m + k = ( q - 2p ) n

Among m, n, k, p, q, the first two are properties of the given list. If we can show that there is at least one set of values for k, q, p that makes this equation true we show that the hypothesis is correct.

One such solution set is as follows:

p = 0

q = m

k = m n - m

We can verify that these values work as follows:

m + k = ( q - 2p ) n  

=> m + mn - m = ( m - 2*0) n

=> mn = mn

For this set, i is

i = m + p n + k

=> m + 0 * n + mn - m = mn

Of course, you should see that this is not necessarily the smallest i possible. In other words, tortoise and hare might have already met before many times. However, since we show that they meet at some point at least once we can say that the hypothesis is correct. So they would have to meet if we move one of them by 1 step, and the other one by 2 steps at a time.

Now we can go to the second part of the algorithm which is how to find the beginning of the cycle.

Cycle Beginning

Once tortoise and hare meet, let's put tortoise back to the beginning of the list and keep hare where they met (which is k steps away from the cycle beginning).

The hypothesis is that if we let them move at the same speed (1 step for both), the first time they ever meet again will be the cycle beginning.

Let's prove this hypothesis.

Let's first assume some oracle tells us what m is.

Then, if we let them move m + k steps, the tortoise would have to arrive at the point they met originally (k steps away from the cycle beginning - see in the figure).

Previously we showed that m + k = (q - 2p) n.

Since m + k steps is a multiple of cycle length n, hare, in the meantime, would go through the cycle (q-2p) times and would come back to the same point (k steps away from the cycle beginning).

Now, instead of letting them move m + k steps, if we let them move only m steps, the tortoise would arrive at the cycle beginning. Hare would be k steps short of completing (q-2p) rotations. Since it started k steps in front of the cycle beginning, the hare would have to arrive at the cycle beginning.

As a result, this explains that they would have to meet at the cycle beginning after some number of steps for the very first time (very first time because the tortoise just arrived at the cycle after m steps and it could never see hare which was already in the cycle).

Now we know that the number of steps we need to move them until they meet turns out to be the distance from the beginning of the list to the cycle beginning, m. Of course, the algorithm does not need to know what m is. It will just move both tortoise and hare one step at a time until they meet. The meeting point has to be the cycle start and the number of steps must be the distance (m) to the cycle beginning. Assuming we know the length of the list, we can also, compute the length of the cycle of subtracting m from the list length.

Solution 3

Refer this image:

Distance travelled by slowPointer before meeting = x + y

Distance travelled by fastPointer before meeting = (x + y + z) + y = x + 2y + z

Since fastPointer travels with double the speed of slowPointer, and time is constant for both when the reach the meeting point.

So by using simple speed, time and distance relation 2(x+y)= x+2y+z => x+2y+z = 2x+2y => x=z

Hence by moving slowPointer to start of linked list, and making both slowPointer and fastPointer to move one node at a time, they both have same distance to cover .

They will reach at the point where the loop starts in the linked list.

Solution 4

_{Old Monk's simple and under-upvoted answer explains finding the cycle when the fast runner completes only single full cycle. In this answer I explain the case when fast runner has run the loop multiple times before the slow runner enters the loop.}

---

Using the same image:

Let's say the fast runner has run the loop m times before slow and fast meet. This means that:

• Distance run by slow: x + y
• Distance run by fast: x + m(y + z) + y i.e. extra y where they meet

Since fast runs with twice the speed of slow, and that they have been running for same time, it implies that if we double the distance ran by slow, we get the distance ran by fast. Thus,

• 2(x + y) = x + m(y + z) + y

Solving for x gives,

x = (m - 1)(y + z) + z

In real scenario it would mean, x = (m - 1) complete loop runs + an extra distance z.

Hence, if we put one pointer at the start of the list and leave the other one at the meeting point, then moving them by the same speed will result in the in loop pointer completing m - 1 runs of the loop and then meeting the other pointer right at the loop beginning.

Solution 5

It's very very simple. You can think in terms of relative speed. If the rabbit moves two nodes and tortoise moves one node, relative to tortoise rabbit is moving one node(assume tortoise at rest). So, if we move one node in the circular linked list we are sure going to meet at that point again.

After finding the connected point inside the circular linked list, now the problem is reduced to finding the intersection point of two linked list problem.

View more solutions

Comments

[csharpfolk]

Another explanation: marcin-chwedczuk.github.io/…

[gnasher729]

I wonder if anyone can find the start of the cycle easily if Brent's algorithm is used.

[Passionate programmer]

@Jim lewis The meeting point will not be a starting point of course, but as I said shifting one of those two to beginning of linked list and moving both at same speed will make them meet at the starting point of cycle.

[Jim Lewis]

@Passionate: Hope this edit clarifies the situation. The key insight is that the number of (tortoise) steps to the first meeting must be a multiple of the cycle length, and that mu steps from either this position or the start position will take you to the start of the cycle.

[Passionate programmer]

@Jim Lewis It would be great if you could explain about how having i as multiple of loop length results to mu as distance between first meeting point and loop beginning.

[Jim Lewis]

@Passionate: Take mu steps from the start point to get to X_mu, the start of the cycle (by definition of mu). Then if you take i more steps, where i is a multiple of the cycle length, you end up back at the cycle start: X_mu + i = X_mu. But addition is commutative, so this is equivalent to taking i steps to get from the start to the first meeting point X_i, then mu additional steps to get back to X_mu, the start of the cycle.

[Plumenator]

You can't assume that the tortoise travelled exactly x+b-k by the time they meet. Also, I don't understand how you got x+2*b-k for the hare's distance.

[n0nChun]

Because the hare would have traversed the looped part once already to have to met the tortoise.. I didn't explain it there :/

[Ankur Trapasiya]

@JimLewis : i understood the part that i always has to be multiple of cycle length but the step "X_mu + i = X_mu" in which you are adding the value of mu to the i is not clear to me. Well why you added the value of mu to the i ? Can't it be any other value ? That part is not clear to me. It would really a great help if you can elaborate it.

[Jim Lewis]

@ankur: Perhaps it would have been clearer if I had written "X_(mu + i) = X_mu" (with (mu + i) being the subscript). If you start at node X_mu (by definition, the first node of the cycle), then take i steps, you will end up at node X_mu again, since i is an exact multiple of the cycle length. Does that help?

[Ankur Trapasiya]

@JimLewis : Sorry but i am still not smart enough to understand it. Still my mind is not able to understand why the distance is mu from the meeting point to loop start point. why it is not any other distance?

[Jim Lewis]

@ankur: The meeting point is X_i, and we have shown (third paragraph in my answer) that i must be a multiple of the loop length. After mu additional steps past the meeting point, you are now at X_(i + mu). But we have shown that X_(i + mu) = X_(mu + i) = X_mu, because of this special property of i, so mu steps past the meeting point must take you to X_mu, the start of the cycle. Basically modular arithmetic, plus the commutative property of addition.

[Ivan Xiao]

I think there is a small problem in your proof. Since the meeting point i is at some point of the cycle, I think the equation should be i = mu + k + a*lambda and 2i = mu + k + b*lambda, where k is the number of step from cycle start to the meeting point. Subtracting both equations give the same result though.

[MrSham]

I don't think so its true that when they meet that's the starting point see comment below : stackoverflow.com/a/19209858/1744146<br> Please let me know If I am wrong

[Leeor]

Please post the full answer here instead of just a link which may break in the future

[Gopichand]

First part of explanation is flawless. But Second part has a flaw as far as I know. You are assuming that "some oracle says m", but if m is known, you already have the beginning of the cycle. How can you just assume the answer when you never know where is the start of cycle?? Please let me know.

[Srinath]

@Gopichand Read the last para again...you just assume that there is some m (if it is already proved that there is a cycle)..but you don't know the value of m

[discoverAnkit]

I wanted to ask even if the fast pointer is thrice as fast as the slow pointer or four times or n times as fast as the slow pointer, the slow and fast pointer would still meet, right?

[rajaditya_m]

@ankitG : Yes they will meet if we advance it thrice as fast. However they will now meet 2*offset away from the starting node. So to find the location of the start cycle, we will have to move the pointer in the cycle at speed 2x compared to the one in the beginning of the list. Why ? Because now the faster pointer has a 2*offset headstart in the list.

[discoverAnkit]

@rajaditya_m : I am not really concerned about finding the starting node of the cycle here. My question basically is that once both the tortoise and the hare are in the loop, will they necessarily meet irrespective of the speed of the hare? Why? Why not?

[Mido]

Thank you for the explanation. Assuming that we know a linked list is circular, I was wondering why we can't just use a Set to keep track of visited nodes in the linked list? something like this

[Jackson Tale]

@Mido the set solution requires additional O(n) spaces while this one doesn't.

[Hazem]

In the second part (cycle beginning), you said that m + k = (q - 2p) n. But that equation was derived when hare moved at twice the speed of tortoise. Now that they move at the same speed, does the equation still hold?

[Jingguo Yao]

This does not take into account the case that fastPointer travels the cycle n times before slowPointer enters the cycle. Use l to denote the length of the cycle. Distance travelled by fastPointer before meeting = (x + y + z) + y = x + 2y + nl + z. And the resulting relation will be x = nl+z.

[displayName]

@JingguoYao: Here is the explanation for that case.

[siraj]

One doubt.. how its guaranteed that slow and fast will meet before slow takes more than one cycle?

[displayName]

@siraj: Slow won't run in cycles, fast would as it is running faster than slow and will enter the loop before. And it's guaranteed that they would meet. If slow is at j + 1 and fast is at j, they will now meet at j + 2. And if slow is at j and fast at j + 1, it means that they already met at j - 1.

[mayas_mom]

the math still works if slow goes around loop: x+(y+z)m+y = 2(x+(y+z)n+y), where n is # of times around loop for slow before they meet. This solves to (m-2n-1)(y+z)+z=x. Which means starting at meeting point, go around (m-2n-1) times, you are back at meeting point, an then go z, you are at start of loop. And to do this it is the same as starting at the head node and going x nodes.

[displayName]

@mayas_mom: Math may be working out but slow will never be able to go around the loop. It will always be caught either right at the start or somewhere mid-way.

[thispatchofsky]

@displayName - In "Hence, if we put one pointer at the start of the loop"... shouldn't it be "at the start of the list"? It is throwing me off a bit.

[displayName]

@srinivas.naik: You are right. I have corrected my mistake.

[Vikas]

This is the best explanation in simple words. Could you please do the world a favor and edit the Wikipedia page for this algorithm? en.wikipedia.org/wiki/Cycle_detection

[Arpit Jain]

Your Equation m + k = (q - 2p) n can be further simplified to m + k = q*n. This is because the number of loops tortoise takes will always be zero since the hare can never overtake the tortoise without meeting it. Think about it.

[anshul garg]

x = (m - 1)(y + z) + z this can be generalized as loop length is y+z and since are only concerned about position. So x = ((m - 1)(y + z))%(y+z)) + z Which is effectively x=z;

[Warren MacEvoy]

this diagram is over-simple. the fast pointer can move many times through the cycle before the slow pointer reaches it.

[Warren MacEvoy]

They do not necessarily meet at the start of the cycle.

[Warren MacEvoy]

they usually do not meet at the beginning of the cycle

[Warren MacEvoy]

Link to google doc to simulate algorithm: docs.google.com/spreadsheets/d/…

[Warren MacEvoy]

Note that, if N <= C, the iteration stops after C iterations. In any case it must stop in less than N+C steps and is unlikely to stop at the beginning of the cycle.

[displayName]

@WarrenMacEvoy: If you follow the exact steps of the answer, the slow and fast pointer will meet at loop beginning, not the starting point.

[skedastik]

@WarrenMacEvoy At no point did I suggest that they meet at the starting point. They meet again at the start of the cycle as the figures clearly point out.

[Istiaque Ahmed]

@displayName, You said in your comment to siraj: " If slow is at j + 1 and fast is at j, they will now meet at j + 2. And if slow is at j and fast at j + 1, it means that they already met at j - 1". Suppose when slow is at j, fast is at j-m and they will meet at j+k. What is the proof that k<n where n=total step length of the loop ?

[Istiaque Ahmed]

@displayName, " There are only two cases possible - either fast lands over slow in every iteration or it lands over slow in every other iteration. (1/2)" - can you expliain a bit more ?

[AleksandrH]

"Hence, if we put one pointer at the start of the list and leave the other one at the meeting point, then moving them by the same speed will result in the in loop pointer completing m - 1 runs of the loop and then meeting the other pointer right at the loop beginning." Terrible explanation. The two nodes start at the beginning.

[displayName]

@AleksandrH: They start at the head node but after they have met each other inside the loop, then you have to bring one of them to head again and leave other one at the meeting point. And then move both of them one node at a time. That is how they will meet again at the loop beginning. (Feel free to edit and update the answer if you can make it better.)

[displayName]

@Tommy: Yeah.. I tried to understand the solution to this problem from CTCI. But it was so tedious. I understood the solution above in one go. Then after seeing the missing case in the above solution, I ended up writing this addendum.

[Srishti]

@CEGRD In the first part of explanation of how it works, could you please elaborate more on how you derived the solution set consisting of p=0 and especially q=m to satisfy the final equation?

[Abhijit Sarkar]

I tried very hard to appreciate this answer, but this statement makes no sense to me "if we move one node in the circular linked list we are sure going to meet at that point again"

[displayName]

@Warren MacEvoy: It is a good thing that this diagram is simple. It helps to understand the base case. The next case is here. That case is equally simple to understand.

[uzluisf]

@Warren MacEvoy "the fast pointer can move many times through the cycle before the slow pointer reaches it." Isn't the fast pointer that meets the slow pointer at the same place, and not the other way around? It could be perspective though.