Search code examples
c++algorithmlinked-list

Why Floyd's cycle finding algorithm, the tortoise and hare both need to start at the same location?


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;
    }

Solution

  • 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.