Detect and remove a LL Loop: 4 METHODS

There are a lot of approaches that we can use to detect and remove a loop. 

This is the question which is asked in many good companies. So make sure to practice it before going to an interview.

LOOP DETECTION: Floyd Cycle detection algorith is the most commonly used algorith to detect a loop in a linked list. 

Floyd cycle detection algorithm: In this algorithm, we use tortoise and hare pointers. 

Tortoise_pointer-> next; //moves by one unit

hare_pointer->next->next; //moves by 2 units

At the point when both the two-pointer are at the same node, there is a loop. If not there is no loop in the linked list.

Code: to be added later

Method 1 for Loop Removal: 

Let's say we detected the loop and now our task is to remove the loop from the list. We got the common point/node which is also a node of the loop. We will store the address of this common point/node in a pointer say, pointer_2. Put a pointer (say pointer_1) at the head of the Linkedlist. 

Now check for the nodes 1 by 1 if they are reachable to pointer_2. If we are able to find a node which is reachable to the pointer_2, then that node is the starting node of the loop found in the Linked List.

With this starting node we can find the previous node of this node, and make that last node point to NULL. 

For this, we will use two more pointers. We will find the last node of the loop and make it point to NULL. 

last_nodeof_loop->next= NULL;

Idea: the very first node whose next node is visited is the last node.

 

Method 2: By counting the no of nodes of loop

First detect loop using Floyd cycle detection algorithm. Set a pointer on the common node/point found while loop detection. Count the number of loops. Lets say the count is n. 

Fix one pointer to the head and another to a nth node from the node. Move both the pointers at the same pace. Soon they will meet at the starting node of the loop. 

So we got the start node of the loop, the n we can get the last node of the loop. Then make the last node to point to NULL. This is it. 

Method 3: Optimised method of method 2

Without counting the nodes in loop

Let us say we have detected the loop usign floyd cycle detection algorithm. Put slow_pointer on head. Now we will move both the slow and fast pointer with a same pace until they meet again.

Method 4:  Hashing

We will hash the address of the linked list node in an unordered map. We will check if the element already exists in the map. If yes, then we found the start node of the loop. Then we will make the last pointer of the loop to point to NULL.