Algorithms‎ > ‎Lists‎ > ‎

## Detect and Remove Loop in a Linked List

May 9, 2011

Write a function detectAndRemoveLoop() that checks whether a given Linked List contains loop and if loop is present then removes the loop and returns true. And if the list doesn’t contain loop then returns false. Below diagram shows a linked list with a loop. detectAndRemoveLoop() must change the below list to 1->2->3->4->5->NULL.

We recommend to read following post as a prerequisite.

Write a C function to detect loop in a linked list

Before trying to remove the loop, we must detect it. Techniques discussed in the above post can be used to detect loop. To remove loop, all we need to do is to get pointer to the last node of the loop. For example, node with value 5 in the above diagram. Once we have pointer to the last node, we can make the next of this node as NULL and loop is gone.
We can easily use Hashing or Visited node techniques (discussed in the aobve mentioned post) to get the pointer to the last node. Idea is simple: the very first node whose next is already visited (or hashed) is the last node.
We can also use Floyd Cycle Detection algorithm to detect and remove the loop. In the Floyd’s algo, the slow and fast pointers meet at a loop node. We can use this loop node to remove cycle. There are following two different ways of removing loop when Floyd’s algorithm is used for Loop detection.

Method 1 (Check one by one)
We know that Floyd’s Cycle detection algorithm terminates when fast and slow pointers meet at a common point. We also know that this common point is one of the loop nodes (2 or 3 or 4 or 5 in the above diagram). We store the address of this in a pointer variable say ptr2. Then we start from the head of the Linked List and check for nodes one by one if they are reachable from ptr2. When we find a node that is reachable, we know that this node is the starting node of the loop in Linked List and we can get pointer to the previous of this node.

 `#include``#include` `/* Link list node */``struct` `node``{``    ``int` `data;``    ``struct` `node* next;``};` `/* Function to remove loop. Used by detectAndRemoveLoop() */``void` `removeLoop(``struct` `node *, ``struct` `node *);` `/* This function detects and removes loop in the list``  ``If loop was there in the list then it returns 1,``  ``otherwise returns 0 */``int` `detectAndRemoveLoop(``struct` `node *list)``{``    ``struct` `node  *slow_p = list, *fast_p = list;` `    ``while` `(slow_p && fast_p && fast_p->next)``    ``{``        ``slow_p = slow_p->next;``        ``fast_p  = fast_p->next->next;` `        ``/* If slow_p and fast_p meet at some point then there``           ``is a loop */``        ``if` `(slow_p == fast_p)``        ``{``            ``removeLoop(slow_p, list);` `            ``/* Return 1 to indicate that loop is found */``            ``return` `1;``        ``}``    ``}` `    ``/* Return 0 to indeciate that ther is no loop*/``    ``return` `0;``}` `/* Function to remove loop.`` ``loop_node --> Pointer to one of the loop nodes`` ``head -->  Pointer to the start node of the linked list */``void` `removeLoop(``struct` `node *loop_node, ``struct` `node *head)``{``   ``struct` `node *ptr1;``   ``struct` `node *ptr2;` `   ``/* Set a pointer to the beging of the Linked List and``      ``move it one by one to find the first node which is``      ``part of the Linked List */``   ``ptr1 = head;``   ``while``(1)``   ``{``     ``/* Now start a pointer from loop_node and check if it ever``       ``reaches ptr2 */``     ``ptr2 = loop_node;``     ``while``(ptr2->next != loop_node && ptr2->next != ptr1)``     ``{``         ``ptr2 = ptr2->next;``     ``}` `     ``/* If ptr2 reahced ptr1 then there is a loop. So break the``        ``loop */``     ``if``(ptr2->next == ptr1)``        ``break``;` `     ``/* If ptr2 did't reach ptr1 then try the next node after ptr1 */``     ``else``       ``ptr1 = ptr1->next;``   ``}` `   ``/* After the end of loop ptr2 is the last node of the loop. So``     ``make next of ptr2 as NULL */``   ``ptr2->next = NULL;``}` `/* UTILITY FUNCTIONS */``/* Given a reference (pointer to pointer) to the head``  ``of a list and an int, pushes a new node on the front``  ``of the list. */``void` `push(``struct` `node** head_ref, ``int` `new_data)``{``    ``/* allocate node */``    ``struct` `node* new_node =``        ``(``struct` `node*) ``malloc``(``sizeof``(``struct` `node));` `    ``/* put in the data  */``    ``new_node->data  = new_data;` `    ``/* link the old list off the new node */``    ``new_node->next = (*head_ref);` `    ``/* move the head to point to the new node */``    ``(*head_ref)    = new_node;``}` `/* Function to print linked list */``void` `printList(``struct` `node *node)``{``    ``while``(node != NULL)``    ``{``        ``printf``(``"%d  "``, node->data);``        ``node = node->next;``    ``}``}` `/* Drier program to test above function*/``int` `main()``{``    ``/* Start with the empty list */``    ``struct` `node* head = NULL;` `    ``push(&head, 10);``    ``push(&head, 4);``    ``push(&head, 15);``    ``push(&head, 20);``    ``push(&head, 50);` `    ``/* Create a loop for testing */``    ``head->next->next->next->next->next = head->next->next;` `    ``detectAndRemoveLoop(head);` `    ``printf``(``"Linked List after removing loop \n"``);``    ``printList(head);` `    ``getchar``();``    ``return` `0;``}`

Method 2 (Efficient Solution)
This method is also dependent on Floyd’s Cycle detection algorithm.
1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
5) Get pointer to the last node of loop and make next of it as NULL.

Thanks to WgpShashank for suggesting this method.

 `#include``#include` `/* Link list node */``struct` `node``{``    ``int` `data;``    ``struct` `node* next;``};` `/* Function to remove loop. */``void` `removeLoop(``struct` `node *, ``struct` `node *);` `/* This function detects and removes loop in the list``  ``If loop was there in the list then it returns 1,``  ``otherwise returns 0 */``int` `detectAndRemoveLoop(``struct` `node *list)``{``    ``struct` `node  *slow_p = list, *fast_p = list;` `    ``while` `(slow_p && fast_p && fast_p->next)``    ``{``        ``slow_p = slow_p->next;``        ``fast_p  = fast_p->next->next;` `        ``/* If slow_p and fast_p meet at some point then there``           ``is a loop */``        ``if` `(slow_p == fast_p)``        ``{``            ``removeLoop(slow_p, list);` `            ``/* Return 1 to indicate that loop is found */``            ``return` `1;``        ``}``    ``}` `    ``/* Return 0 to indeciate that ther is no loop*/``    ``return` `0;``}` `/* Function to remove loop.`` ``loop_node --> Pointer to one of the loop nodes`` ``head -->  Pointer to the start node of the linked list */``void` `removeLoop(``struct` `node *loop_node, ``struct` `node *head)``{``    ``struct` `node *ptr1 = loop_node;``    ``struct` `node *ptr2 = loop_node;` `    ``// Count the number of nodes in loop``    ``unsigned ``int` `k = 1, i;``    ``while` `(ptr1->next != ptr2)``    ``{``        ``ptr1 = ptr1->next;``        ``k++;``    ``}` `    ``// Fix one pointer to head``    ``ptr1 = head;` `    ``// And the other pointer to k nodes after head``    ``ptr2 = head;``    ``for``(i = 0; i < k; i++)``      ``ptr2 = ptr2->next;` `    ``/*  Move both pointers at the same pace,``      ``they will meet at loop starting node */``    ``while``(ptr2 != ptr1)``    ``{``        ``ptr1 = ptr1->next;``        ``ptr2 = ptr2->next;``    ``}` `    ``// Get pointer to the last node``    ``ptr2 = ptr2->next;``    ``while``(ptr2->next != ptr1)``       ``ptr2 = ptr2->next;` `    ``/* Set the next node of the loop ending node``      ``to fix the loop */``    ``ptr2->next = NULL;``}` `/* UTILITY FUNCTIONS */``/* Given a reference (pointer to pointer) to the head``  ``of a list and an int, pushes a new node on the front``  ``of the list. */``void` `push(``struct` `node** head_ref, ``int` `new_data)``{``    ``/* allocate node */``    ``struct` `node* new_node =``        ``(``struct` `node*) ``malloc``(``sizeof``(``struct` `node));` `    ``/* put in the data  */``    ``new_node->data  = new_data;` `    ``/* link the old list off the new node */``    ``new_node->next = (*head_ref);` `    ``/* move the head to point to the new node */``    ``(*head_ref)    = new_node;``}` `/* Function to print linked list */``void` `printList(``struct` `node *node)``{``    ``while``(node != NULL)``    ``{``        ``printf``(``"%d  "``, node->data);``        ``node = node->next;``    ``}``}` `/* Drier program to test above function*/``int` `main()``{``    ``/* Start with the empty list */``    ``struct` `node* head = NULL;` `    ``push(&head, 10);``    ``push(&head, 4);``    ``push(&head, 15);``    ``push(&head, 20);``    ``push(&head, 50);` `    ``/* Create a loop for testing */``    ``head->next->next->next->next->next = head->next->next;` `    ``detectAndRemoveLoop(head);` `    ``printf``(``"Linked List after removing loop \n"``);``    ``printList(head);` `    ``getchar``();``    ``return` `0;``}`