Tuesday, May 31, 2016

Understanding Finding loop entry in LinkedList

This is an ugly way to understand it, but it works for me.

Assuming there are K steps from start to entry of loop, assuming loop's length is O.

let p-slow steps 1 step each time, p-fast stenos 2 steps each time.

The first time they meet, let's say the meeting point is called M, distance between e and M is m. slower pointer has moved x circles starting from e, faster pointer has moved y circles starting form e, then we have

slower pointer moving distance = K+xO+m
faster pointer moving distance = K+yO+m

We know K+yO+m=2(K+xO+m)
so that K=(y-2x)O-m
that is equivalent to K=(y-2x-1)O+(O-m)
let's name O-m=m', which is distance from M to e.

K-m'=(y-2x-1)O
This means after m' steps, reset of K is certain number of circles.
We know after m' steps, slow pointer will do circles starting from e.

So if have another slow pointer starting from head, they must meet at e after moving K steps since after m' steps, the moves are number of circles.

No comments: