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:
Post a Comment