CODEWITHSUNDEEP
javaalgorithmfloyd-cycle-finding
Vimal
Vimal

Reputation: 87

Question about logic of removing loop in linked list

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!

Upvotes: 2

Views: 92

Answers (2)

ialam
ialam

Reputation: 173

Diagram for reference

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

Upvotes: 2

Pablo
Pablo

Reputation: 446

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.

Upvotes: 1

Related Questions