How can we find the starting node of a loop in link list?

Question

According to the Floyd's cycle finding algorithm, the point where tortoise and hare meets explains the circular nature in the link list.

To find the starting node in the cycle we initialize tortoise pointer to head of the list and starts incrementing hare and tortoise pointer by one unit. The point where they meet denotes the starting node of the cycle.

Please tell me how it works for the given situation.

The link list flows as:

1->2->3->4->5->6->7->8->3

possible duplicate of [Explain how finding cycle start node in cycle linked list work?](http://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work) (and various other questions) — Fred Foo, Jun 04 '12 at 11:45
yea..i have seen that but if you will see the 2nd answer and apply the above situation then that answer is not satiable. — som, Jun 04 '12 at 11:59
With Floyd's, you're looking for a cycle in a sequence. The example sequence you gave contains no cycles. Could you explain what kind of "circular nature" are you looking for, perhaps we're not speaking of the same thing? — Greg Kramida, Jun 04 '12 at 13:09

score 15 · Accepted Answer · edited Sep 27 '14 at 14:47

15

Let's see.

You position the hare and the tortoise at 1, and let them run, the hare twice as fast as the tortoise.

At the zeroth step, both are at 1. At the first step, the tortoise moves to 2 and the hare moves to 3, and so on.

So the hare and the tortoise meet at 7.

Now place the tortoise at the beginning, and let them run again, now with the same speed.

1 7
2 8
3 3

So they indeed have met at the first element of the cycle.

And that's how it works for the given situation.

edited Sep 27 '14 at 14:47

Piyush Mattoo

15,454
6
47
56

answered Jun 04 '12 at 14:06

n. m. could be an AI

112,515
14
128
243

Strictly speaking, mathematically, you're right - assuming we're using some mapping function continuously to get the next element, i.e. some recursive function of the previous element. Given a linked list in practice, however, this would only work assuming the list is circularly-linked. – Greg Kramida Jun 04 '12 at 14:17
@Algomorph: sorry, I have not a slightest idea. 1 points to 2, 2 points to 3, 3 points to 4, 4 points to 5, 5 points to 6, 6 points to 7, 7 points to 8, 8 points back to 3. Here's a circularly linked list before your very eyes. What else is needed? – n. m. could be an AI Jun 04 '12 at 14:35
When i = 4, and 2i = 8 for this example, everything is fine. But what happens when i = 5? How did you determine that the "hare" element at i=10 is 5? What you're saying makes total sense if you have a function that determines the value of the next element based on the previous, i.e. f(3) = 4, and f(4) = 5. What doesn't make sense is how you obtain 5 by calling tail.next().next(). @som stated he was only given a linked list in his example, not a mapping function. +1 for mathematical correctness, however, I should have said "the linked list", not "sequence" in my response. – Greg Kramida Jun 04 '12 at 14:51
@Algomorph: let me say it again. **There's a circular linked list before your eyes**. Item number 8 points to item number 3. **It's the same item number 3 that was seen right after item number 2**. It is just shown in a different place. There's no tail in this list. – n. m. could be an AI Jun 04 '12 at 14:58
@n.m.: you are correct dude, but what happens if you first start incrementing fast pointer and then slow pointer. The situation will be like 1 1, 3 2, 5 3, 7 4, 3 5, 5 5 – som Jun 05 '12 at 03:12
@som: 3 5 then 5 5? Why, somebody got a new set of brakes? – n. m. could be an AI Jun 05 '12 at 06:00
@n.m: Okay, I concede that if this is the case, you are correct. I suppose I just didn't quite understand what "linked list" was supposed to mean - apparently, it's a whole graph, which contains a cycle, not just a linked list. – Greg Kramida Jun 05 '12 at 11:34

score 14 · Answer 2 · answered Jun 04 '12 at 18:31

OK, let's keep it simple.

Say you have two runners A and B. A move forward by 1 node each step, B moves by 2 nodes.

If it's a cyclic list, they will finally meet each other.

At that time

Say the distance A has moved so far is m, so for B it's 2m

Also note that

 m = a + b
2m = a + b + k * lengthOfLoop

Because for B, it has moved whatever distance A has moved, plus k(some number we don't care) of loops. a is the distance before the loop point, b is the distance A moved after the loop point.

Then we have (after some math)

a = k * lengthOfLoop - b

Now we put B back to the head of the list, and reduce his speed to 1.

For B, it's a nodes away from the loop point. For A, he already passed the loop point by b, and according to the equation above, he is also a nodes away from the loop point.

So, after a more steps, A and B will meet again at the loop point.

Greg Kramida · Answer 3 · 2012-06-04T14:55:01.400

5

Okay, direct answer: The [EDIT: linked list, not sequence] you gave contains no cycles. Here's what will happen. In the first part of the algorithm, the tortoise and hair will start out at x1=2 and x2=3, respectively. Then they will advance to x2=3 and x4=5. Then to x3=4 and x6=7. Then to x4=5 and x8=3. Then the hare will cease to advance, since there isn't anything beyond x8, and the algorithm will yield that no cycles were found.

Below I compiled a little GIF that shows Floyd's cycle-finding applied to a different sequence, that does contain cycles.

Floyd's algorithm in action.

edited Jun 04 '12 at 14:55

answered Jun 04 '12 at 14:04

Greg Kramida

4,064
5
30
46

1

Nice illustration, however, his example does contain a cycle, – n. m. could be an AI Jun 04 '12 at 14:08
dude the example i gave contains a cycle..the next pointer of 8th node contains the address of 3rd node. Isn't it a cycle?? – som Jun 05 '12 at 02:52

score 0 · Answer 4 · edited Jun 20 '20 at 09:12

Consider two pointers: fast pointer(moving two nodes at a time) and slow pointer(moving one node at a time). Both starts moving from head of linked list.

After some time, the slow pointer enters the loop on traveling k nodes from head, at that time fast pointer would have traveled 2k nodes the head of the list. So, this means that the fast pointer points to the k'th node from the slow pointer.

Example: (fig 1)

Now they keep moving till they meet somewhere in the loop. When they will meet they will be far from the beginning of the loop by exactly the same number of nodes as fast pointer was from slow pointer in the starting of loop ( i.e. the distance of the starting node of the loop from the node where fast pointer and slow pointer meet is k elements(or nodes). And k is also the distance of starting node of loop from head of the linked list .

(fig 2)

So, we start moving a pointer from head and one pointer from meeting point of fast pointer and slow pointer. Since the distance of starting node of the loop is k from both these point, so they will meet in their kth step at begining node of the loop

score 0 · Answer 5 · answered Jan 20 '21 at 21:06

Assume you have a linked list with a length of 9, position the tortoise at index 0, and the hare at index 1.
The hare should move at a speed of x2, and the tortoise at a speed of x1, so that the next time they move, the hare would be at index 3 and the tortoise at index 2
They continue to move this way until the value on the hare is equal to the value on the tortoise.
At this point, move the hare back to the head of the linked list (such that the hare is now at the head of the linked list and the tortoise is at the index/position it met the hare), this time it should only move x1, the same speed as the tortoise.
Start moving the hare and the tortoise again, as mentioned previously, the hare and the tortoise should move at a speed of x1, such that if the position the hare and the tortoise met was at index 6, this next move should result in the hare being at index 1 and the tortoise at index 7.
The next point that the hare and tortoise meet again is the start of the loop on this linked list.

How can we find the starting node of a loop in link list?

5 Answers5