What is Loop in Linked List?
In a standard singly linked list, the last node always points to NULL. If you traverse such a linked list, the traversal will end at the last node. That means you can not go anywhere from the last node. Here is an example of a standard linked list.
Loop in a linked list exists if the last node points to any other node in the list. If you have a loop in linked list, you can traverse the list endlessly. In this case, you will hit all or some of the nodes again and again.
In the linked list below, the last node (10) is pointing to another node (9) in the list.
If you traverse the list, you’ll find some nodes (9, 18, 6 and 10) again and again.
In this article, we’ll see how to detect and remove a loop in a linked list in C programming language.
Create a Linked List with Loop
We’ll first create a linked list with loop for our experiments.
#include <stdio.h>
#include <stdlib.h>
struct node{
int val;
struct node *next;
};
void print_list(struct node *head)
{
printf("H->");
while(head)
{
printf("%d->", head->val);
head = head->next;
}
printf("|||\n");
}
void insert_front(struct node **head, int value)
{
struct node * new_node = NULL;
new_node = (struct node *)malloc(sizeof(struct node));
if (new_node == NULL)
{
printf("Failed to insert element. Out of memory");
}
new_node->val = value;
new_node->next = *head;
*head = new_node;
}
void create_loop(struct node *head)
{
struct node *tmp = head;
while(tmp->next) tmp = tmp->next;
tmp->next = head->next;
}
void print_loop(struct node *head)
{
int n = 25;
printf("H->");
while(n--)
{
printf("%d->", head->val);
head = head->next;
}
printf("\n");
}
void main()
{
int count = 0, i, val;
struct node * head = NULL;
printf("Enter number of elements: ");
scanf("%d", &count);
for (i = 0; i < count; i++)
{
printf("Enter %dth element: ", i);
scanf("%d", &val);
insert_front(&head, val);
}
printf("Original List: ");
print_list(head);
printf("Creating loop...\n");
create_loop(head);
printf("Printing list with loop:\n");
print_loop(head);
}We created a standard linked list by inserting elements at the front of the list. The called called the create_loop() function to create the loop. This function traversed up to the last node and pointed the last node to the second node of the list.
Here is the output of the program.
From this output we can see that before creating the loop traversal ended at node 10. But after creating the loop, some nodes (9, 18, 6 and 10) are coming again and again. We stopped printing after 25 nodes. Otherwise, it would go endlessly.
Detect and Remove Loop in a Linked List
We’ll first use Floyd algorithm for this purpose.
Detect a Loop
- Point slow and fast pointer to the first node where head is pointing to.
- Continue to move slow pointer by one node (slow = slow->next) and fast pointer by two nodes (fast = fast->next->next).
- If at any point slow or fast becomes NULL, stop the traversal. There is no loop in the linked list.
- If at any point, slow and fast meet together (slow == fast), there is a loop in the list.
Remove the Loop
To remove the loop, we need to figure out the last node of the list and point that node to NULL. In the above algorithm, slow and fast pointers meet somewhere in the loop which might not be the start or end node of the loop.
- Point the near pointer to the first node. And point the far pointer as far as the size of the loop. Keep a prev pointer just before far pointer.
- Keep moving above three pointers, until near meets far. The meeting point would be the start of the loop and prev would be the end of the loop.
- Assign NULL to prev.
Note: To place the far pointer as far as the size of the loop, we can first point the far pointer to the first node. Point another pointer, say ptr, to next of any loop node (say where slow and fast met). Keep moving far and ptr until ptr comes back to the loop node.
#include <stdio.h>
#include <stdlib.h>
struct node{
int val;
struct node *next;
};
void print_list(struct node *head)
{
printf("H->");
while(head)
{
printf("%d->", head->val);
head = head->next;
}
printf("|||\n");
}
void insert_front(struct node **head, int value)
{
struct node * new_node = NULL;
new_node = (struct node *)malloc(sizeof(struct node));
if (new_node == NULL)
{
printf("Failed to insert element. Out of memory");
}
new_node->val = value;
new_node->next = *head;
*head = new_node;
}
void create_loop(struct node *head)
{
struct node *tmp = head;
while(tmp->next) tmp = tmp->next;
tmp->next = head->next;
}
void print_loop(struct node *head)
{
int n = 25;
printf("H->");
while(n--)
{
printf("%d->", head->val);
head = head->next;
}
printf("|||\n");
}
struct node * detect_loop(struct node *head)
{
struct node *slow = head;
struct node *fast = head;
while(slow && fast->next && fast->next->next)
{
fast = fast->next->next;
if (slow == fast)
{
printf("Linked list has a loop.\n");
return slow;
}
slow = slow->next;
}
return NULL;
}
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 * loop_node;
loop_node = detect_loop(head);
if(loop_node) remove_loop(head, loop_node);
}
void main()
{
int count = 0, i, val;
struct node * head = NULL;
printf("Enter number of elements: ");
scanf("%d", &count);
for (i = 0; i < count; i++)
{
printf("Enter %dth element: ", i);
scanf("%d", &val);
insert_front(&head, val);
}
printf("Original List: ");
print_list(head);
detect_loop(head);
printf("Creating loop...\n");
create_loop(head);
printf("Printing list with loop");
print_loop(head);
printf("Removing loop...\n");
detect_and_remove_loop(head);
printf("List after removing loop:\n");
print_list(head);
}This program is same as the previous one except it has the detect_loop() and remove_loop() functions.
Here is the output of the program.
From this output, we can see that after removing the loop, we got the original list that ends with 18 node. So the last node again points to NULL.
Detect and Remove Loop using Another List
We can have a simpler solution but with higher memory requirement and time complexity (O(N2)). Here we’ll maintain a list of already traversed nodes (traversed_list).
- Traverse the list starting from head. For every node, check the node is already present in traversed_list or not.
- If the node (pointer) is not in traversed_list, then put the pointer of the node in the traversed_list and move to the next node.
- If the current node exists in the traversed_list that means the linked list has a loop. The the current node is the starting node of the list.
- Point the previous node to NULL to remove the loop.
struct node_ptr
{
void *val;
struct node_ptr *next;
};
void insert_front1(struct node_ptr **head, void* value)
{
struct node_ptr * new_node = NULL;
new_node = (struct node_ptr *)malloc(sizeof(struct node_ptr));
if (new_node == NULL)
{
printf("Failed to insert element. Out of memory");
}
new_node->val = value;
new_node->next = *head;
*head = new_node;
}
int is_present(struct node_ptr *head, void *val)
{
while(head)
{
if (head->val == val) return 1;
head = head->next;
}
return 0;
}
void detect_and_remove_loop(struct node *head)
{
struct node_ptr *traversed_list = NULL;
struct node *ptr = head;
while(ptr)
{
if(is_present(traversed_list, ptr->next))
{
printf("Linked list has a loop.\n");
/*Removing loop*/
ptr->next = NULL;
delete_list(traversed_list);
return;
}
insert_front1(&traversed_list, ptr);
ptr = ptr->next;
}
delete_list(traversed_list);
printf("Linked list does not have any loop.\n");
}New data structure struct node_ptr is used for linked list of the traverse nodes (traversed_list). Here the value part is also a pointer instead of node. We have new insert function insert_front1() to create the list. The detect_and_remove_loop() function implements the logic discussed above.
