Question about logic of removing loop in linked list

Question

Below is the code after finding that loop exists in the list using Floyd's slow fast algorithm.

How can we be sure that begin and tortoise will meet at the beginning of the loop?

Node begin = head;
tortoise = tortoise.next;
while (begin != tortoise) {
    begin = begin.next;
    if (tortoise.next == begin) {        // Find the position of the loop and mark the node as null

        tortoise.next = null;
        return;
    }
    tortoise = tortoise.next;
}

Any help would be appreciated!

Is [this](https://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work) what you are asking? — Pablo, Oct 03 '19 at 11:51

ialam · Answer 1 · 2019-10-03T11:32:25.020

2

Let's see the First part before the code posted by you.

Consider

a slow (tortoise) and a fast pointer (hare). fast pointer moves with twice the speed of slow pointer so when slow pointer has moved distance "d" then fast has moved distance "2d".
Length from starting point to intersection point is x (refer diagram).
They meet at a random point of length y from point of intersection (refer diagram).
From meeting point to intersection point consider the length to be z (refer diagram).
the length of loop is y+z;
when slow and fast meet. slow has covered distance x+y (say d)
fast has covered distance x+y+z+y (which will be 2*d)
2*d= x+2y+z
2(x+y)= x+2y+z
2x+2y=x+2y+z
x=z (Proved)

Now coming to the code you posted.

since it's proved that x will be equal to z after first meeting point (given hare is twice as fast as tortoise) then moving one pointer from beginning and one pointer from first meeting point lead to the point of intersection (i.e start of loop).

edited Oct 03 '19 at 11:32

answered Oct 03 '19 at 11:19

ialam

153
1
7

I don't think this approach will work with longer lengths. Can you give any other example with longer length of loop or before loop. – Vimal Oct 03 '19 at 11:46
1

my example is on variables (I have never considered longer or shorter loops etc). It will always hold true for any given value of x,y,z. Please do mix and match of x,y and z and then please let me know if it makes point to you. – ialam Oct 03 '19 at 12:10
1

now lets day X is long and loop is small (x > y+z). then z will become n*z (where n is the number of times the loop has been traversed). Till the time pointer from beginning will come to the intersection point, the pointer inside the loop will traverse n times the loop to meet the other pointer at the beginning of loop. I think this was your doubt right? Since it's a loop you don't need to worry about how many times it was traversed as in a circle there will be no change in distances of each node from each other. – ialam Oct 03 '19 at 12:52

score 1 · Answer 2 · answered Oct 03 '19 at 10:37

1

The idea is that the two pointers are moving at different speeds. So the next of tortoise might jump one element, while the next of begin (I think it is usually referred as hare) might jump more. If you increase both of them and there is a loop, one will catch up to the other one at some point.

answered Oct 03 '19 at 10:37

Pablo

377
1
14

The code snippet pasted by me is for cycle removal after the cycle has been detected. And my doubt is about this code. I can paste the rest of the code if you want. – Vimal Oct 03 '19 at 11:32

Question about logic of removing loop in linked list

2 Answers2