Detect a loop in linked list | Find the start of the loop and remove the loop

Program to detect a loop in linked list and removing the loop from the linked list is discussed here. Firstly, let us learn what a loop in a linked list means.

 

What is a loop in a linked list?

Loop in a linked list means the list can be traversed endlessly. If you traverse a linked list with a loop, the nodes in the linked list will be visited again and again.

 

Program to detect a loop in linked list and removing the loop

// C program to detect a loop in linked list and removing a loop from the list

#include
#include

struct node
{
int data;
struct node *next;
};

void print_list(struct node *head)
{

while(head)
{
printf(“%d “, head->data);
head = head->next;
}

printf(“\n\n”);
}

void insert_front(struct node **head, int dataue)
{
struct node * new_node = NULL;

new_node = (struct node *)malloc(sizeof(struct node));

if (new_node == NULL)
{
printf(“\nUnable to allocate memory\n”);
}

new_node->data = dataue;
new_node->next = *head;

*head = new_node;
}

void create_loop(struct node *head)
{
struct node *temp = head;

while(temp->next)
temp = temp->next;

temp->next = head->next;
}

void print_loop(struct node *head)
{
int n = 25;

while(n–)
{
printf(“%d “, head->data);
head = head->next;
}

printf(“\n\n”);
}

void detect_loop(struct node *head)
{
struct node *slow = head;
struct node *fast = head;

while(slow && fast->next && fast->next->next)
{
if ((slow == fast->next) || (slow == fast->next->next ))
{
printf(“\nLinked list has a loop.\n”);
return;
}

slow = slow->next;
fast = fast->next->next;
}

printf(“\nLinked list does not have any loop.\n”);
}

void remove_loop(struct node *head, struct node *loop_node)
{
struct node *near = head;
struct node *far = head;
struct node *ptr = loop_node;
struct node *prev = NULL;

while(ptr->next != loop_node)
{
ptr = ptr->next;
far = far->next;
}

prev = far;
far = far->next;

while(near != far)
{
prev = far;
far = far->next;
near = near->next;
}

prev->next = NULL;
}

void detect_and_remove_loop(struct node *head)
{
struct node *slow = head;
struct node *fast = head;

while(slow && fast->next && fast->next->next)
{
if ((slow == fast->next) || (slow == fast->next->next ))
{
printf(“\nLinked list has a loop\n”);
remove_loop(head, slow);
return;
}

slow = slow->next;
fast = fast->next->next;
}

printf(“\nLinked list does not have any loop\n”);
}

int main()
{
int n, i, data;
struct node * head = NULL;

printf(“\nEnter number of elements : “);
scanf(“%d”, &n);
printf(“\nEnter the elements : ” );
for (i = 0; i < n; i++)
{
scanf(“%d”, &data);
insert_front(&head, data);
}

printf(“\nThe Linked List is : “);
print_list(head);
detect_loop(head);

printf(“\nCreating loop…\n”);
create_loop(head);
printf(“\nPrinting list with loop\n”);
print_loop(head);

printf(“\nRemoving loop…\n”);
detect_and_remove_loop(head);

printf(“\nList after removing loop:\n”);
print_list(head);
}

// C++ program to detect a loop in linked list and removing the loop from the list

#include
#include
using namespace std;

struct node
{
int data;
struct node *next;
};

void print_list(struct node *head)
{

while(head)
{
cout << head->data << ” “;
head = head->next;
}

cout << endl;
}

void insert_front(struct node **head, int data)
{
struct node * new_node = NULL;

new_node = (struct node *)malloc(sizeof(struct node));

if (new_node == NULL)
{
cout <<“\nUnable to allocate memory\n”;
}

new_node->data = data;
new_node->next = *head;

*head = new_node;
}

void create_loop(struct node *head)
{
struct node *temp = head;

while(temp->next)
temp = temp->next;

temp->next = head->next;
}

void print_loop(struct node *head)
{
int n = 25;

while(n–)
{
cout << head->data << ” “;
head = head->next;
}

cout << endl;
}

void detect_loop(struct node *head)
{
struct node *slow = head;
struct node *fast = head;

while(slow && fast->next && fast->next->next)
{
if ((slow == fast->next) || (slow == fast->next->next ))
{
cout <<“\nLinked list has a loop\n”;
return;
}

slow = slow->next;
fast = fast->next->next;
}

cout <<“\nLinked list does not have any loop\n”;
}

void remove_loop(struct node *head, struct node *loop_node)
{
struct node *near = head;
struct node *far = head;
struct node *ptr = loop_node;
struct node *prev = NULL;

while(ptr->next != loop_node)
{
ptr = ptr->next;
far = far->next;
}

prev = far;
far = far->next;

while(near != far)
{
prev = far;
far = far->next;
near = near->next;
}

prev->next = NULL;
}

void detect_and_remove_loop(struct node *head)
{
struct node *slow = head;
struct node *fast = head;

while(slow && fast->next && fast->next->next)
{
if ((slow == fast->next) || (slow == fast->next->next ))
{
cout <<“\nLinked list has a loop\n”;
remove_loop(head, slow);
return;
}

slow = slow->next;
fast = fast->next->next;
}

cout <<“\nLinked list does not have any loop\n”;
}

int main()
{
int n, i, data;
struct node * head = NULL;

cout <<“\nEnter number of elements : “;
cin >> n;
cout <<“\nEnter the elements : ” ;
for (i = 0; i < n; i++)
{
cin >> data;
insert_front(&head, data);
}

cout <<“\nThe Linked List is : “;
print_list(head);
detect_loop(head);

cout <<“\nCreating loop…\n”;
create_loop(head);
cout <<“\nPrinting list with loop\n”;
print_loop(head);

cout <<“\nRemoving loop…\n”;
detect_and_remove_loop(head);

cout <<“\nList after removing loop:\n”;
print_list(head);
}