Detect loop in a linked list
time complexity O(n)
What I have done is take a set then insert the addresses of each node in the set so if there will be loop in the linked list then address that has to be insert will detect second time .
The method to detect the loop is pretty straightforward but the length of the code is more than it has to be because I added an extra function that allows you to create the loop by selecting the position where you want to create the loop.
create_loop_in_a_linked_list(n1,n2) is the extra function in this function you have to provide two values the data for the new node and the position where you have to create loop.
After creating your loop you can check from the function Detect_loop_in_a_linked_list().
if you apply Detect_loop_in_a_linked_list() without creating the loop in the linked list then it will gave an output as no loop in the linked list.
we can also find the position where the loop is found .The code will be update soon..
#include<stdio.h>
#include<stdlib.h>
#include<set>
using namespace std;
struct node
{
char data;
struct node *next;
}*head;
void insert(int num)
{
struct node* temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;
temp->next=NULL;
if(head==NULL)
{
head=temp;
}
else
{
struct node* temp1=head;
while(temp1->next!=NULL)
{
temp1=temp1->next;
}
temp1->next=temp;
}
}
void create_loop_in_a_linked_list(int num,int n2)
{
int i;
struct node* temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;
struct node* temp1=head;
while(temp1->next!=NULL)
{
temp1=temp1->next;
}
temp1->next=temp;
struct node* temp2=head;
for(i=0;i<n2;i++)
{
temp2=temp2->next;
}
temp->next=temp2;
}
void display()
{
struct node *temp2;
temp2=head;
while(temp2!=NULL)
{
printf("%d ",temp2->data);
temp2=temp2->next;
}
}
int Detect_loop_in_a_linked_list()
{
std::set<node*> check_loop;
std::set<node*>::iterator it;
struct node* temp=head;
check_loop.insert(temp);
temp=temp->next;
while(temp!=NULL)
{
if(check_loop.find(temp)!=check_loop.end())
{
return 1;
}
check_loop.insert(temp);
temp=temp->next;
}
return 0;
}
int main()
{
int i,num;
int pos;
int n1,n2;
struct node *n;
head=NULL;
while(1)
{
printf("\nList Operations\n");
printf("===============\n");
printf("1.Insert\n");
printf("2.Display\n");
printf("3.create a loop in a linked list by inserting at last and pointing it to any previous element\n");
printf("4.detect a loop\n");
printf("5.Exit\n");
printf("Enter your choice : ");
if(scanf("%d",&i)<=0){
printf("Enter only an Integer\n");
exit(0);
} else {
switch(i)
{
case 1: printf("Enter the number to insert : ");
scanf("%d",&num);
insert(num);
break;
case 2: if(head==NULL)
{
printf("List is Empty\n");
}
else
{
printf("Element(s) in the list are : ");
}
display();
break;
case 3:
printf("Enter the element and the position where the loop has to be made\n");
scanf("%d %d",&n1,&n2);
create_loop_in_a_linked_list(n1,n2);
break;
case 4:
if(Detect_loop_in_a_linked_list())
printf("Loop detected\n");
else
printf("No loop detected\n");
break;
case 5:
return 0;
default: printf("Invalid option\n");
}
}
}
return 0;
}
No comments:
Post a Comment