How to detect/find Loop in a Linked List in C Code

/*C Linux code for detecting Loop/cycle in as a linked list.
Take two pointers advance one by one and the other by 2 nodes.
If these pointers meet then loop is present else not.*/
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head=NULL;
void insert(struct node **,int d);
void display(struct node *);
int findLoop(struct node *);

int main()
{
int result;
insert(&head,10);
insert(&head,20);
insert(&head,30);
insert(&head,40);
insert(&head,50);
insert(&head,60);
display(head);
printf("\nCreate some loop.\n");
head->next->next->next->next->next=head;
result=findLoop(head);
if(result==1)
{

printf("\nYes,Loop Present in Linked List.\n ");
}
else
{

printf("\nNo,Loop Present in Linked List.\n ");
}
printf("\n");
return 0;
}
void insert(struct node **head,int d)
{
struct node *newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=d;
newnode->next=(*head);
(*head)=newnode;
}
void display(struct node *head)
{
while(head)
{
printf("%d ",head->data);
head=head->next;
}
}
int findLoop(struct node *head)
{
struct node *slow=head;
struct node *fast=head;
while((fast->next!=NULL) && (fast->next->next!=NULL))
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
//printf("\nYes,Loop Present in Linked List.\n ");
return 1;
}
}
return 0;
}
/*
When run with loop outpt is:

50 40 30 20 10
Create some loop.
Yes,Loop Present in Linked List.

When run commenting loop outpt is:
50 40 30 20 10
No,Loop Present in Linked List.
*/

No comments:

Post a Comment