Hare and Tortoise - To Find Start of Loop in Linked List

A tiny bit of background

"Hare and Tortoise!" - cool name, right? Well, the algorithm is even cooler! Frankly, there were points in my life when I was fuming at this algo, and it was just sitting there, legs crossed on the couch's arm, smoking a cigar, smiling smoothly, and watching me suffer... But! Things changed, and now I am the one on the couch, and it's my pet now (preferably with a leash, no offense to pet lovers! Though it does feel a bit offensive, sorry!)

What Is This Algo??

It's composed of one thing- an awesome and brilliant logic. Its aim is to find the starting node of the loop in a linked list, if one exists.

The Brilliant Logic Behind The Scenes -

It is common knowledge that "Hare runs faster than Tortoise". Similarly, we have a hare pointer and a tortoise pointer in our algorithm. Since 'tortoise' is too lengthy and we're too lazy, let's go with the conventional names- fast pointer and slow pointer. (Because it's ugly to call them hare and slow pointers.)

See how they run- (oh, I love that movie!)

fast_ptr goes two steps and slow_ptr takes one at a time. If no loop is present, fast_ptr would eventually be null (or at least its next node will be). Else the fast_ptr would eventually catch up with slow_ptr (like Cap does with Sam Wilson). Now let's take a break and reflect on these two. (Sipping milk:)...) Yeah, break time's over, let's warm up:

If fast_ptr or its next node becomes NULL: return NULL (coz there's no 'loop' for us to return the starting point of the 'loop')
Else we know there's a loop and that both fast_ptr and slow_ptr are inside the loop, each pointing to (some) same node

Time for a dash of magic (or some logic)

Say, the length from head until the start_of_loop(S) is 'a' and the extra distance from start_of_loop till meeting_point(M) is 'b'. Let the remaining unnamed length be 'y'.

• Now Here's what I call a 'good observation': The extra length travelled by fast_ptr is equal to a+b. Because the fact that fast_ptr took 2 steps while slow_ptr took only one means that the distance traveled by fast_ptr is twice that traveled by slow_ptr.
• Distance traveled by slow_ptr = a+b. So, the distance traveled by fast_ptr is 2(a+b).
• Like slow_ptr, fast_ptr also covered a distance of a+b initially. And then it traveled 'an extra distance y and b' (say some 'n' times) to meet the slow_ptr.
• So basically, the extra distance covered by fast_ptr was n(y+b) which is equal to a+b. (2(a+b)-(a+b) = a+b)

$n(y+b)=a+b => a = n(y+b)-b$ | This equation suggests that going through the loop n times, while skipping a distance of 'b', is same as traveling a distance of 'a'.

• The above statement can also be interpreted in another way- if some 'ptr1' is to travel a distance 'a+b' and a 'ptr2' is to travel ny+(n-1)b starting from M, they would point to same node (meeting_point) at the end of the journey.
• But, since both are travelling at same speeds (one step at a time), they would already be pointing to same nodes long before they reach meeting_point.
• To conclude, both the pointers would have pointed to same node since the start_of_loop. So, the first node where "ptr1==ptr2" would be the start node of the loop.
• Therefore, if the hare_ptr starts from the head node again, this time slowing down, and taking one step at a time (because it's tired running all his life), and the slow_ptr resumes from meeting_point and try to go over the loop, both will meet at the start_of_loop.

Algorithm in C/C++

Node *startNodeOfLoop(Node *head)
{
    Node *fast = head, *slow = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
        if(fast==slow) {
            fast = head;
            while(fast!=slow){
                fast = fast->next;
                slow = slow->next;
            }
            return fast;
        }
    }
    return NULL;
}

Epilogue

Ah, Man! that was exhaustingly lengthy (longer than I intended). Nonetheless, I really hope you are on the couch with the algorithm's leash in your hand. The Hare & Tortoise algorithm described above is also known as Floyd's Cycle-Finding Algorithm. It's a brilliant and efficient solution to the problem of detecting cycles in a linked list. I believe that it is algorithms like these that remind me where true beauty resides while solving problems the programmer's way. Adios!!