Algorithms-Floyd’s Algorithm(Tortoise And The Hare)

Algorithms are a part of everyday life. They surround us and encompass us in our everyday life. From waking up, brushing your teeth, washing your face, taking a poop, take a shower, put your clothes on, eat your breakfast, get your daily Covid-19 tests, try to study, get on your online class, ignore your online class and play clash of clans, regret ignoring my online class from 5 months ago, have fun with Yuvan playing Apex Legends, Rocket League and Titanfall, and the other things that you do to fill your day. Everything that follows a routine is an algorithm, and only through repetition are things actually completed and taken a full grasp of. With every day, every iteration and every repetition, and every set of instructions that take place is an algorithm.

Today we are going to write a function that determines if a singly linked list is circular and if it is, we are going to return the node where the cycle begins. This solution is based off of Robert Floyd’s algorithm, first discovered in the 1970’s.

Floyd’s Algorithm (Tortoise and the Hare Algorithm) is a pretty simple

algorithm with 2 pointers that are your main point of interest, over a linked list.

Lets say you have 2 pointers named Hare and Tortoise at the head of your linked list. You update your Hare with +2 to the index, with the Tortoise with only a +1 to the index per iteration. Your Hare basically has double the speed compared to your Tortoise. In every iteration, you compare the value of the Tortoise and the value of the Hare with each other. IF the address of the Hare and the Tortoise are the same, then we can infer that a cycle is present in the linked list. This is due to the fact that Tortoise and Hare cannot be at the same address since both are getting updated with different values and hence we can come to the conclusion that a cycle is present in this linked list.

The importance of finding a cycle in the linked list is because in the absence of not knowing that a cycle exists in the linked list, you would never be able to traverse the whole of a linked list, and would be stuck in an infinite loop.

Something as simple as the Floyd’s Algorithm can help avoid scenarios where your computer can end up in a run-time error.

The time complexity of this is O(n), since only one whole traversal of the linked list is required. For the Space complexity, it only has O(1), since no extra space is needed.

The algorithm is to start two pointers, slow and fast from head of linked list. We move slow one node at a time and fast two nodes at a time. If there is a loop, then they will definitely meet. This approach works because of the following facts.

1) When slow pointer enters the loop, the fast pointer must be inside the loop. Let fast pointer be distance k from slow.

2) Now if consider movements of slow and fast pointers, we can notice that distance between them (from slow to fast) increase by one after every iteration. After one iteration (of slow = next of slow and fast = next of next of fast), distance between slow and fast becomes k+1, after two iterations, k+2, and so on. When distance becomes n, they meet because they are moving in a cycle of length n.

For example, we can see in below diagram, initial distance is 2. After one iteration, distance becomes 3, after 2 iterations, it becomes 4. After 3 iterations, it becomes 5 which is distance 0. And they meet.

Another example for this is:

Consider a slow and a fast pointer. fast pointer moves with twice the speed of slow pointer. so when slow pointer has moved distance “d” then fast has moved distance “2d”.

now consider the length of loop is y + z;
distance before loop is x
now when slow and fast meet
slow has covered distance d= x + y
fast has covered distance 2*d= x + y + z + y

2*d = x + 2y + z
2( x + y )= x+2y+z
2x + 2y = x + 2y + z
x = z
so this shows after getting meeting point if one pointer is placed to the beginning. then moving both with equal distance. they will meet at the start of loop.

One thing to always remember when tackling any concept of algorithms is to know how every aspect of the algorithm fits in with all the other components. The reach of every component fits inside the other and helps gel the algorithm smoothly.