560 views
0

How to find loop in linked list? How to find start of the loop ?

0  take two pointers slow and fast. keep incrementing the slow by one and fast by two. if there is a loop then eventually they meet. Why?

if there is a loop then fast  should come back and it should either jump or meet slow pointer. But fast can never cross on slow before meeting slow. (why?)

Let us assume every thing is set for fast to cross the slow pointer now

Since slow is going to move at least one step ahead, fast is at least one step behind slow, to cross slow at any time fast has to make at least three steps

one step to balance the lagging, one step to balance the slow’s step, one step to cross the slow. But fast can move exactly two steps. hence it can not cross.

Before meeting with the fast, slow would make at most one round in the loop

(why?)

think about the position of fast when slow comes in to the loop first time, So that fast would meet slow as late as possible.

definitely that would be immediately next position after slow. (why?) the more far the fast is from slow then the more closer to slow it would be. (circular philosophy).

so let me assume fast next to slow.

so when slow makes half round then though fast makes one full round, still fast can not cross slow as fast is now around old position of slow(one more than that).

when slow makes another half round then by that time fast which is half round behind slow can cover it and can make another half round (why?)

since the speed of fast is 2 times to speed of slow.

Huhhhhhh. Lets use some maths here. if slow and fast meets at point z.

From the beginning of the story, total distance traveled by slow is x+z ( we just proved that it made atmost one round)

total distance traveled by fast is 2* dist traveled by slow. in other way it is x+ n(y+z) + z, where n is no of rounds  made by fast  before meeting slow.

2(x+z )= x+n(y+z) + z

x= n(y+z)+z-2z= n(y+z)-z= (n-1)(y+z)+1(y+z)-z= (n-1)(y+z)+y

now if we keep slow pointer at start and fast pointer at meeting point then increment them one step each simultaneously

exactly after x steps slow comes to start of the loop(see picture) then by that time (x = (n-1)(y+z) + y) fast , which is in the loop, would take (n-1)(y+z)+y steps; where (n-1)(y+z) is equal to making n-1 rounds in the loop and coming back to the same position, then followed by y which moves fast pointer y steps ahead of its current position in the picture, will move fast to start of the loop.

finally when start and fast meets in this process then it would be start of the loop.

When it is coming to the time complexity, since slow is making only one round in the loop, assuming list size n, there are n pointer increments by slow and 2n pointer increments by fast, over all it would be at most 3n, which is O(n).