Killing the Loop in a Link

In the last post we discussed a way to find the loop in a link. Once we know that there is a loop in our linked list, first thing we should do if we want our linked list to be realistic and usable, is to remove the loop.

How do we kill the beast? I guess if we know where the loop starts, we will be able to burn its tell (set the next pointer of the magic node to null).

Lets get started.

What we already know? 

From our little stint in the last post in this category, we know for sure that there is a loop in the below linked list.

Linked List with a Loop

We also have our hare and tortoise pointers pointing to an element inside the loop. Like so.

As the hare and tortoise story goes, the hare stops in between the race thinking that the tortoise can never catch or overtake him. Eventually the tortoise through its sheer perseverance catches hare, overtakes him and wins the race. Nice inspirational story.

In our case, the ends don't meet as we don't have an end to our linked list. And by the way, our hare has read that story and thus he never stops. Which means he will continue to loop crossing the tortoise again and again until we let him stop. Which also means that at this point when both hare and tortoise are pointing to the same node, if we let our hare run and at each node increment loopsize by 1, by the time hare catches tortoise back, we will have the size of our loop.

What we already know? Update 1.

• That there is a loop in our linked list.
• And the size of the loop (in this case 4). 

Now lets start at the beginning again. Set hare and tortoise both to point to the start of the linked list and then give our hare a heads up of exactly the loopsize. (Yeah, this time no matter what, we will let our hare win the race. Why should tortoise have all the fun?). This makes hare and tortoise loopsize apart - make a mental note of it, this will come handy.

What we already know? Update 2.

• That there is a loop in our linked list
• The size of the loop
• And two pointers one pointing at the start of the linked list and another loopsize away from it.

Now advance both hare and tortoise exactly by one node until both point to the same node at which point, tortoise will be at the start of the loop and hare will be at the end of the loop. And yeah, its a loop so both start and end are same :). Also while you are advancing the hare pointer, keep track of the previous value, something like this:

previous = hare;

hare = hare.next;

What we already know? Update 3.

• That there is a loop in our linked list
• The size of the loop
• The start of the loop.
• The Element at the end of the loop that points back to start.

Now killing this loop is simple. As I said earlier, just burn the tail. Okay, in technical terms, doing something like previous.next = null (removing the red pointer in the above figure); should do the trick. Here's our final linked list without a loop in it.

I hope you enjoyed this post. And I was able to express the algorithm in a way that will stick to your grey matter.

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

Until then,

Happy Learning!

Banyan Bat

P.S.

After successfully understanding the above algorithm to find and eliminate a loop in a linked list, you have an important and very handy tool under your belt sometimes referred to as a Two Pointer Algorithm. This algorithm can be easily used in a lot of other problems. One such example is:

• Find Nth node from the end of the linked list.

I would like to leave you with the problem to find a solution. You can google for a ready made algorithm to solve this problem, but if you think on the grounds of what we just discussed in the last two posts, it might stick around your head a bit longer.

Also, this post pretty much concludes our discussions related to the singly linked list data structure. Although we will come back to the topic as and when it feels like a right thing to do :).