DILI #10: A Classic In Programming

HARE - TORTOISE ALGORITHM

Also known as Floyd’s cycle finding algorithm, is a literal classic in Linked List. Using a simple technique of one fast moving pointer (the hare) and one slow moving one (the tortoise), one can see if there's a loop or not in a given Linked List. Also, it has an interesting property that will wow-ed any of you like how it wow-ed me.

Because in a singly Linked List, you can only traverse like one-way road, many pointers are needed. For example, a simple program to reverse a linked list needs up to 3 pointers to navigate and reverse it:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while(cur != nullptr){
            ListNode* forw = cur->next;
            cur->next = prev;
            prev = cur;
            cur = forw;
        }
    return prev;
    }

};

The above was a small exercise in Leetcode. Anyways, that is to show most Linked List problems require multiple pointers and Floyd's Hare and Tortoise algorithm also follows suit.

The algorithm starts by moving the two pointers to the first node of the linked list. The slow pointer then moves one node at a time, while the fast pointer moves two nodes at a time. If the linked list does not contain a cycle, the fast pointer will eventually reach the end of the list and stop. However, if the linked list does contain a cycle, the fast pointer will eventually catch up to the slow pointer. Or the hare will eventually catch up to the tortoise.

But the crazy part comes later, Floyd's algorithm's property can pinpoint the start of cycle/loop. The start of the cycle can be found by moving the tortoise to the start, then move both tortoise and the hare, who's still at the meeting point, until they both meet again. That point is the start of the cycle. NOW THAT'S COOL, IS IT NOT?

Let's declare some variables:

X: the distance from the start of Linked List to the start of cycle.
Y: the distance from the start of the cycle to the meeting point.
C: one full trip around the cycle.
t: the amount of time the tortoise loops.
h: the amount of time the hare loops.

With that, we can say:

The tortoise traveled a distance of X + Y + t*C.
The hare traveled a distance of X + Y + h*C.

But because the hare is twice as fast as the tortoise, it would travel double the distance given the same time. So we have the equation:

X + Y + t*C = 2(X + Y + h*C)

After simplification, we have:

X + Y = (t + h)*C or X = (t + h)*C - Y.

But going a full round trip any number of time is equal to going a full round trip one time or just think trigonometrically. So we have X = C - Y.

So, the distance from the start of Linked List to the start of cycle will equals to the meeting point to the start of the cycle. Hence, we have the claim above. Very neat!

REFERENCES:
GeeksforGeeks
LeetCode