Decoding the Hare-Tortoise Algorithm for detecting a loop in a Linked List in a very simpler fashion and understanding it’s time complexity !
For detecting a cycle in a linked list , we use the hare tortoise or the famous Floyd Warshall Algorithm.
The algorithm states that there will be two pointers.
A hare pointer and a tortoise pointer.
As the name suggests , the hare pointer will move twice the speed of the tortoise pointer at a single iteration(Check code snippet below).
If there exists a cycle in the linked list, they will always meet at a point in the cycle.
But ever thought why it always works?
So in the above diagram, 0 is the starting point of the loop.
The hare will run 2 times the distance of the tortoise. So when they meet ,
distance covered by the hare = 2 * distance covered by the tortoise.
Why will they always meet if there is a cycle ?
After the hare has entered the cycle it will lag behind the tortoise , but it will catch up soon, since at every traversal , it is catching up with the tortoise by one node i.e their distance difference is decreasing by 1 with every traversal.
Now let us think differently. Let us assume that the tortoise is standing still and the hare is coming to him at a speed of 1. So the hare will catch up eventually , right?
The same thing is happening here. If you are considering relative speed and distance , actually the hare is coming to the tortoise at a speed of 1 while the tortoise is standing still. It is the same scenario of the hare moving by 2 and the tortoise by 1.
Now the time complexity to check whether there exists a loop or not and to find it’s intersection point is O(N + K) ~ O(N) where K is the length of the cycle.
Why?
Let’s suppose K is the length of the cycle. So at a certain point , after both the hare and the tortoise have entered the cycle , there will always come a point when the hare is behind the tortoise and will do a catching up.
So as I just explained , imagine the situation like this that the hare is moving at a speed of 1 node per traversal and the tortoise is standing still (that’s the same as the hare moving by 2 nodes and the tortoise by 1). Then at most , the hare has to traverse a maximum of K -1 distance to catch up with the tortoise. And prior to that the hare has traversed the entire list. Hence complexity is O(N+K) ~ O(N).
Now finding the start of the cycle.
So let’s suppose
Start of linked list(head) = A
start of cycle = C
Intersection point = H.
AC = F
CH = a
HF = b
Distance traversed by the hare when they both meet = F + a + b + a.
Distance traversed by the tortoise when they both meet = F + a.
Now we know that the distance traversed by the hare is twice as the distance traversed by the tortoise.
2(F+a) = F + a + b + a
2F + 2a = F + 2a + b
F = b.
Therefore distance from the head to the start of the cycle of the linked list = distance from the intersection point to the start of the cycle of the linked list.
Hence if we have one pointer stationed at head and another one at intersection point and they both move at the same speed , then they will both meet at C (starting point of the cycle) as they have the same distance.
Now time complexity for finding the intersection point as discussed above = O(N)
Time complexity for finding the start of the cycle = O(f) or O(b)
Hence total time complexity = O(N) + O(f) ~ O(N).
Hope it helps.
Feel free to connect with me over LinkedIn or Instagram for any further queries.
Also checkout my YouTube Channel.
Image Credits : Leetcode.
