I understand that why tortoise and hare will meet if hare moves at speed 2 and tortoise moves at speed of 1 if there is one cycle. Because if the cycle length is k, the (2-1)*t (distance between tortoise and hare) will eventually be dividable k. But what I don't understand is why in order to find the entry point both tortoise and hare need to start at the same location in the beginning.
Here is what I implemented correctly. But just by changing the initial condition the finding of entrance point will loop forever.
if(!head || head->next==nullptr) return nullptr;
ListNode* fast=head->next->next;
ListNode* slow=head->next; // if changing to slow=head or fast=head->next the second loop below will loop forever.
while(fast!=nullptr && fast->next!=nullptr
&& slow!=nullptr && fast!=slow) {
fast = fast->next->next;
slow = slow->next;
}
if(fast!=nullptr && slow!=nullptr && fast==slow) {
slow = head;
while(fast!=slow){
fast = fast->next;
slow = slow->next;
}
return fast;
} else {
return nullptr;
}
Assume the circle length is n
, the length from start to the entry point of circle is k
, the first loop took time t
till both pointers meet.
We will have (2t-k) = (t-k) (mod n)
, where 2t-k
is the hare's distance on the circle and t-k
is the tortoise's distance on the circle.
Let's say tortoise have moved q=t-k
on the circle. Using modular arithmetic:
t = 0 (mod n)
q+k = 0 (mod n)
Let's define int l>=0
so that q+k=l*n
. k=l*n-q
which means the distance k
from start to the entry point is the distance tortoise going forward with length l*n-q
which also arrive at the entry point.