Saturday, August 17, 2013

Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop

DEFINITION 
Circular linked list: A (corrupt) linked list in which a node's next pointer points 
to an earlier node, so as to make a loop in the linked list. 
EXAMPLE 
Input: A - > B - > C - > D - > E - > C [the same C as earlier] 
Output: C 

#include <stdio.h>
#include <stdlib.h>
 
typedef struct LinkList
{
    int data;
    struct LinkList *next;
}List;
 
void CreateList(List **Head,int value)
{
    List *ptr=NULL,*node=(List*)malloc(sizeof(List));
    node->data=value;
    node->next=NULL;
    if(*Head==NULL)
    *Head=node;
    else
     {ptr=*Head;
      while(ptr->next)
      ptr=ptr->next;
      ptr->next=node;
         
     }
}
 
List *CorruptNode(List *Head)
{
    List *sptr=Head,*fptr=Head;
    if(!Head)return NULL;
    
    while(fptr->next!=NULL)
    {
        fptr=fptr->next;
        if(fptr->next!=NULL)
        fptr=fptr->next;
        else
        break;
        sptr=sptr->next;
        if(fptr==sptr)
        {
            fptr=Head;
            while(fptr!=sptr)
            {
                fptr=fptr->next;
                sptr=sptr->next;
            }
        return fptr;
        }
    }
return NULL;
}
 
 
main()
{  
List *Head=NULL,*Head1=NULL,*Head2=NULL;
int i=0,value,n=3;
printf("Enter the no. of elements in 2nd list ");
scanf("%d",&n);
for(i=0;i<n;i++) {  scanf("%d",&value);  CreateList(&Head1,value); }
printf("Enter the no. of elements in 2nd list ");
scanf("%d",&n);
for(i=0;i<n;i++)                     
{
 scanf("%d",&value);
 CreateList(&Head2,value);
}
 
Head=Head1;
while(Head1->next!=NULL)
Head1=Head1->next;
List *temp;
temp=Head1;
Head1->next=Head2;
while(Head2->next!=NULL)
Head2=Head2->next;
Head2->next=temp;   //creating corrupt node as List1 last node 
temp=CorruptNode(Head);
if(temp)
printf("corrupt one is= %d",temp->data);
else
printf("No corrupt node");
return 0;
}

No comments:

Post a Comment