Find and Remove loop in a Linked List
Question:
Find and Remove loop in a singly linked list.
Logic:
- Create two pointer slow and fast both are pointing to head.
- Move slow pointer one step and fast pointer two steps forward.
- Both slow and fast pointer will meet one point, if loop exists
- Assign head value to slow, then move both slow and fast one step forward
- There meeting point is the loop’s starting point and then point fast->next = NULL
- In some case both head and fast will be same, need to move fast pointer till the starting of loop
- Print the result of removed loop in linked list
Explanation:
Find Loop:
Remove loop:
Program:
#include<stdio.h> #include<stdlib.h> typedef struct Node{ int value; struct Node *next; }Node; /*print the elements*/ void printList(Node *head) { while(head) { printf("%d ",head->value); head = head->next; } } /*function to create a new node into the list*/ Node* addNode(int value) { Node *temp = (Node*)malloc(sizeof(Node)); temp->value = value; temp->next = NULL; return temp; } /*find and remove loop in linked list*/ void findAndRemoveLoop(Node* head) { Node *slow = head; Node *fast = head; while(fast->next) { fast = fast->next->next; slow = slow->next; /*found the loop*/ if(slow == fast) break; } if(slow == fast) { slow = head; /*Both head and fast pointing to same node*/ if(slow == fast) { /*traverse to loop starting point*/ while(fast->next != slow) fast = fast->next; } else { /*traverse to loop starting point*/ while(fast->next) { if(fast->next == slow->next) break; fast = fast->next; slow = slow->next; } } fast->next = NULL; } } void main() { Node *head = addNode(1); head->next = addNode(2); head->next ->next = addNode(3); head->next->next->next = addNode(4); head->next->next->next->next = addNode(5); head->next->next->next->next->next = addNode(6); head->next->next->next->next->next->next = addNode(7); /*Creating loop pointing to 3rd node*/ head->next->next->next->next->next->next->next = head->next->next; findAndRemoveLoop(head); printList(head); }