/* How would you detect a loop in a linked list & remove it? */
#include <stdio.h>
#include <malloc.h>
typedef struct singlelink node;
struct singlelink
{
int data;
node *next;
};
void append(node **q,int num);
void display(node *temp);
void append(node **q,int num)
{
node *temp=*q,*r;
r = (node *)malloc(sizeof(node));
r->data = num;
r->next = NULL;
if(temp==NULL) *q=r;
else
{
while(temp->next!=NULL)
temp = temp->next;
temp->next = r;
}
}
void display(node *temp)
{
printf("\nThe list:\n");
while(temp)
{
printf("%d ",temp->data);
temp=temp->next;
}
}
void createloop(node *q);
void createloop(node *q)
{
node *temp=q;
node *node2=NULL;
node2=temp->next;
while(temp->next !=NULL)
{ temp=temp->next;}
temp->next=node2;
}
#define DEBUG2 1
void removeloop(node *p, node *tmp);
void removeloop(node *p, node *tmp)
{
node *temp1=p;
node *temp2=p;
unsigned int cnt=1,i;
/* Count the no. of nodes in the loop */
while(temp1->next != temp2)
{
temp1 = temp1->next;
cnt++;
}
/* Fix one pointer to head & the other to cnt^th node from head */
temp1=temp2=tmp;
for(i=0;i
temp2=temp2->next;
/* Move both pointers at the same pace, they will meet at the loop starting node */
while(temp1 != temp2)
{
temp1=temp1->next;
temp2=temp2->next;
}
/* Get pointer to the last node of loop & make next of it as NULL */
temp2=temp2->next;
while(temp2->next != temp1)
temp2 = temp2->next;
temp2->next=NULL;
}
/* Floyd cycle detection algorithm */
void findloop(node *tmp);
void findloop(node *tmp)
{
/* Have 2 pointers to start of the linked list.
Increment one pointer by 1 node and the other by 2 nodes.
If there's a loop, the 2nd pointer will meet the 1st pointer somewhere.
If it does, then you know there's one.
*/
node *p,*q;
p=q=tmp;
while(p && q && q->next)
{
p=p->next;
q=q->next->next;
if(p==q)
{
printf("Loop detected..\n");
removeloop(p,tmp);
return;
}
}
}
int main(void)
{
node *head=NULL;
int i;
for(i=0;i<10;i++)
append(&head,i);
display(head);
createloop(head);
printf("\nOK...\n");
findloop(head);
display(head);
return 0;
}
/*
void findloop(node *tmp)
{
// Have 2 pointers to start of the linked list.
// Increment one pointer by 1 node and the other by 2 nodes.
// If there's a loop, the 2nd pointer will meet the 1st pointer somewhere.
// If it does, then you know there's one.
node *p,*q;
p=tmp;
q=p->next;
while(p!=NULL && q!=NULL)
{
if(p==q)
{
printf("Loop detected..\n");
removeloop(p,tmp);
return;
}
p=p->next;
q=(q->next)?(q->next->next):(q->next);
}
}
*/
