Pages

Monday, 26 August 2013

Detect And Remove Loop in Singly linked List in C

Hi This program is about implementation of Detect and solve looping problem in singly linked list.

If you have any doubt regarding this program or any concept of C then please send me at khimanichirag@gmail.com or post a comment.

suggestion always appreciable


      #include<stdio.h>  
      #include<conio.h>  
      typedef struct node  
      {  
            int data;  
            struct node *link;  
      }node;  
      node *first=NULL,*last;  
      void solve(node *,node *);  
      void checkloop();  
      void main()  
      {  
           int i=0;  
           node *temp;  
            printf("Enter the link list data");  
            do  
            {  
                 clrscr();  
                  temp=(node*)malloc(sizeof(node));  
                 i++;  
                 if(first==NULL)  
                 {  
                        first=temp;  
                        last=temp;  
                        last->link=NULL;  
                 }  
                 else  
                 {  
                        last->link=temp;  
                        last=temp;  
                        last->link=NULL;  
                 }  
                       last->link=first;  
                       printf("\nEnter the %d element",i);  
                       scanf("%d",&(last->data));  
                       printf("\nYou want to enter more data(Y/N)");  
                 }while(getch()=='y');  
                 checkloop();  
           }  
      void checkloop()  
      {  
                 int flag=0;  
                 node *fast,*slow,*temp;  
                 fast=first;  
                 slow=first;  
                 while(fast!=NULL && slow!=NULL)  
                 {  
                        fast=(fast->link)->link;  
                        slow=slow->link;  
                        if(fast==slow)  
                        {  
                         flag=1;  
                         break;  
                        }  
                 }  
                 if(flag==1)  
                 {  
                       printf("\n\n\tlink list contains loop");  
                       solve(fast,slow);  
                 }  
                 else  
                        printf("\nloop nthi vo bhai");  
                 getch();  
      }  
      void solve(node *fast,node *slow)  
      {  
            int i=1,j;  
            node *temp;  
            fast=fast->link;  
            while(fast!=slow)  
            {  
                   fast=fast->link;  
               i++;  
            }  
            fast=slow=first;  
            for(j=0;j<i;j++)  
            {  
                  fast=fast->link;  
       }  
       while(fast!=slow)  
       {  
            fast=fast->link;  
            slow=slow->link;  
       }  
       for(j=0;j<i-1;j++)  
       {  
             fast=fast->link;  
       }  
            fast->link=NULL;  
            printf("\n\n\nafter solving looping problem Your list is:");  
            temp=first;  
            while(temp!=NULL)  
            {  
                   printf("%d ",temp->data);  
                   temp=temp->link;  
            }  
      }  

No comments:

Post a Comment