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

Answer 1

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

Answer 2

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.

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 .

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

Answer 3

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.

1 1
2 3
3 5
4 7
5 3
6 5
7 7 

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.

Answer 4

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.

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