@rubyfrea Yes, it should be nN + A + B = 2(A + B), I don't know why everybody is saying N = A + B, try 0->1->2->3->4->5->6->7->8->9->6, A should go 2 more cycle when they meet.
Actually, we can get nN - B = A, which is what we want. Since nN is what fast point goes longer than B and slow point has ready finished B in a cycle N, so slow point only needs to go nN - B, then he can reach A. So we set another point from head, then let it move nN - B, which is A. Then it reaches the entering-cycle point.
let the distance before loop starts be 9
let loop size be 4
when slow one enters loop, fast one has traveled 18 steps.
18 - 9 = 9 steps inside loop
the position of the fast one is 9 % 4 = 1 inside the loop.
slow one's position is 0 inside the loop.
we can say fast one is 3 steps behind the slow one because 4 - 1 = 3.
fast's relative speed to slow is 1, so it takes 3 turns to catch slow. which means slow and fast meet at turn 9 + 3 = 12.
at turn 12. fast has traveled 24 steps, slow has traveled 12 steps. the diff is 12, which is a multiple of the size of the loop
yes it is a little tricky, draw it on a paper, the biggest difference this solution and Linked List Cycle I is that is has included a third pointer. when there is a single cycle, every time fast and slow pointer meets the detector pointer move one stop further, this make sure that eventually the slow pointer will meet detector pointer. and at that time the detector pointer is where the cycle begins
A bit explaination.
Provide the X is the length from head to the start point of circle and Y is the length of the circle. We know slow moves t, while fast moves 2t. They meet at K where is the length from the start point of the circle.
Then we have :
t = X + nY + K
2t = X + mY + K
, then we get
X+K = (m-2n)Y
which means when they meet at K, the length from K to start point of the circle is just the X. At this moment, we use a head pointer to move by the same step (=1), and they must meet at the start point of the circle which we want.
One further step to make it more clear:
X = (Y - K) + (m - 2n - 1)Y
which means by finishing the rest length of the circle and some number of circle lengths, the traveled distance is equal to X.