Dejavu : Finding a loop in a link

The linked list data structure we discussed in my last post in this category is really nice for sequential data. Insertion and deletion is also nice and simple. There is one problem though. If you want to go to the nth node in the linked list, you have to start from the first node and move one node at a time to your node. What if your node is the last node? You will have to start from the first node and traverse the entire list to get to your node.

Suppose you have the following linked list at hand and you want to go to the node Museum which is the last node. You will have to traverse through the entire list before you can get to it.

A simple Linked List

Okay, I know you love The link so much that you are ready to compromise and are OK with this tedious traversal. But the problem doesn't end there.

Me: Consider the following list. Try traversing through it.

Linked List with a Loop

The Link Fan: What's the big deal here? Here I go: Chocolate, Apple, Table, Shoe, Museum, Apple, Table, Shoe, Museum, Apple. Hold on, I feel like I have been here before, I can feel the word Apple coming again. Is it Dejavu?

Me: My friend, you are not in a Matrix and this isn't Dejavu. What you are feeling is a cycle (or a loop) in a linked list. And you were able to notice it because you are Neo, the one or at least a human, if that gives you any pride. But The Matrix (a computer program of-course) will not be able to detect this cycle and will continue to traverse through this list until it runs out of its resources (Only if Neo new this trick, he could have broke the Matrix in no time and there would not have been a need for all that machine war).

Is that what you want? Of-course not. Not in the real world not of The Wachowski brothers.

Then we must find a way to detect this cycle thingy and if possible, a way to get rid of it.

So lets first try to detect the loop.

• Let's start simple, if the link is empty, it cannot have a loop. So we are good there.
• If there is only one node which points back to start, you know that there is a loop.
• Now if there are more nodes, we need something to detect a loop.

We will use an algorithm called a "Two pointers algorithm". This is also called a "Hare and tortoise Algorithm" because one of the pointers is slow while the other one is fast.

So lets get started, if there are two or more nodes, start the tortoise pointer at the first node and the hare pointer at the second node. Now we will continuously advance the tortoise pointer by 1 node and the hare pointer by two nodes (You see? Hare is faster than the tortoise).

If there is a loop in our linked list, at one time both the hare and the tortoise will point to the same node (In the real Hare and Tortoise story, the hare stops and rests because he underestimates the tortoise. Our hare here is honest as god, it will loop indefinitely if you don't ask it to stop. So, unless there is a loop, our hare and tortoise will never cross each other.). If that happens, you can be sure that there is a loop in your linked list and terminate the traversal.

If there is no loop in the linked list, the hare will eventually point to the end of the link(hare = null) or in case where there are even number of nodes in the linked list, you would not be able to complete the step hare = hare.next.next because hare.next is null (in other words, you would not be able to advance hare by 2 nodes because there is only one node before you hit the end of linked list).

To try the above scenario, remove museum node from the above linked list without a loop.  The hare can only be advance once(when it points to shoe) before hare.next is null.

Lets see if that works:

In our linked list with Dejavu, the hare and tortoise will have following stages during their traversal.

Tortoise and Hare on loop

If we remove the loop and run our algorithm (Linked list with odd number of nodes), it works something like this:

Tortoise and Hare on a straight highway

So this is how you find a loop in the linked list so that you can avoid running out of resources while traversing through a list that never ends.

I hope you enjoyed this post. And I was able to express the algorithm in a way that will stick to your grey matter. Also, do let me know if you think there is a better solution to this problem.

As usual, comments/appreciation/criticism (a constructive one of course) everything is most welcome and appreciated.

In the next post, we will discuss how to get rid of this loop. 

Until then,

Happy Learning!

Banyan Bat