Friday, April 8, 2011

Splitting a list with 2n nodes into two separate and equal lists


Program

# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
void split(struct node *p, struct node **q, int n)
    {
       struct node *temp;
      int i =1;
     temp = p;
            while( i < n)

                              {
                    temp = temp->link;
                    i++;
                              }
     *q = temp->link;
     temp->link = p;
             temp = *q;
            while(temp->link != p)
         temp = temp ->link;
      temp->link = *q;
   }

   struct node *insert(struct node *p, int n)
   {
   struct node *temp;
   /* if the existing list is empty then insert a new node as the
starting node */
   if(p==NULL)
   {
      p=(struct node *)malloc(sizeof(struct node)); /* creates new node
data value passes
   as parameter */

      if(p==NULL)
      {
   printf("Error\n");
          exit(0);
      }
      p-> data = n;
      p-> link = p; /* makes the pointer point to itself because it is
a circular list*/
       }
       else
       {
         temp = p;
    /* traverses the existing list to get the pointer to the last node of
it */
   while (temp-> link != p)
      temp = temp-> link;
       temp-> link = (struct node *)malloc(sizeof(struct node)); /*
creates new node using
          data value passes as
            parameter and puts its
           address in the link field
           of last node of the
           existing list*/
         if(temp -> link == NULL)
         {
      printf("Error\n");
            exit(0);
         }
         temp = temp-> link;
         temp-> data = n;
         temp-> link = p;
      }
      return (p);
   }

   void printlist ( struct node *p )
   {
    struct node *temp;
     temp = p;
    printf("The data values in the list are\n");
      if(p!= NULL)
             do
               {
               printf("%d\t",temp->data);
               temp=temp->link;
               } while (temp!= p);
      else
            printf("The list is empty\n");
   }

   void main()
   {
         int n,num;
         int x;
         struct node *start = NULL ;
         struct node *start1=NULL;
         printf("Enter the value of n \n");
         scanf("%d",&n);
         num = n;
         n*=2;
         /* this will create a circular list with 2n nodes*/
      while ( n-- > 0 )
         {
      printf( "Enter the data values to be placed in a node\n");
             scanf("%d",&x);
             start = insert ( start, x );
         }
         printf("The created list is\n");
         printlist ( start );
         split(start,&start1,num);
         printf("The first list is:\n");
         printlist(start);
         printf("The second list is:\n");
         printlist(start1);
   }

No comments:

Post a Comment