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:
[code lang=”c”]
#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);
}
[/code]
