Saturday, September 3, 2011

Merging of sorted linked lists


/*Merging of sorted linked lists  */

#include <stdio.h>
#include <stdlib.h>

typedef struct node
 { int data;
   struct node *next;
 }node;
node *merge(node *l1,node *l2);
node *create_normal();
node *create_sorted();
void print(node *head);
void sort(node *head);
void main()

 {
   int op1,op2;
   node *head1,*head2,*head3;
   // Accepting second linked list

   printf("\n Enter first Linked list\n");
   printf("\nSelect option");
   printf("\n 1)Accepting data to create normal linked list and then sort it");
   printf("\n 2)Accepting data and sorting it while creation:\n");
   scanf("%d",&op1);
   switch(op1)
{
case 1:printf("\n\nCreating Normal(unsortrd) linked list \n");
head1=create_normal();
printf("\nFirst LInked list(Before Sorting):");
print(head1);
sort(head1);
printf("\nFirst Linked list(After Sorting):");
print(head1);
break;
case 2:printf("\n\nCreating sorted linked list \n");
head1=create_sorted();
printf("\nFirst Linked list:");
print(head1);
break;
default : printf("\n Invalid input ");
exit(0);
}
   // Accepting second linked list

   printf("\n Enter second Linked list\n");
   printf("\nSelect option");
   printf("\n 1)Accepting data to create normal linked list and then sort it");
   printf("\n 2)Accepting data and sorting it while creation:\n");
   scanf("%d",&op2);
   switch(op2)
{
case 1:printf("\n\nCreating Normal(unsortrd) linked list \n");
head2=create_normal();
printf("\nSecond LInked list(Before Sorting):");
print(head2);
sort(head2);
printf("\nSecond Linked list(After Sorting):");
print(head2);
break;
case 2:printf("\n\nCreating sorted linked list \n");
head2=create_sorted();
printf("\nSecond Linked list:");
print(head2);
break;
default : printf("\n Invalid input ");
exit(0);
}

   head3=merge(head1,head2);
   printf("\nFinal List:");
   print(head3);
 }

node *merge(node *l1,node *l2)
   { node *l,*p;
     l=NULL;
     if(l1==NULL)
return(l2);
     if(l2==NULL)
return(l1);
     //insert the first data
     if(l1->data<l2->data)
{
l=p=l1;
l1=l1->next;
}
     else
{
l=p=l2;
l2=l2->next;
}
     while(l1!=NULL && l2!=NULL)
       {
if(l1->data < l2->data)
   {
p->next=l1;
l1=l1->next;
p=p->next;
   }

else
   {
p->next=l2;
l2=l2->next;
p=p->next;
   }

      }
      if(l1!=NULL)
  p->next=l1;
      else
  p->next=l2;

    return(l);
  }
 node *create_normal()
  {
    node *head=NULL,*p;
    int n,x,i;
    printf("\nNumber of nodes:");
    scanf("%d",&n);
    printf("\nEnter data:");
    for(i=1;i<=n;i++)
     {
scanf("%d",&x);
if(head==NULL)
{
p=head=(node*)malloc(sizeof(node));
p->next=NULL;
}
       else
{
p->next=(node*)malloc(sizeof(node));
p=p->next;
p->next=NULL;
}
       p->data=x;
    }
   return(head);
 }
node *create_sorted()
  { node *head=NULL,*p,*q;
    int n,x,i;
    printf("\nNumber of nodes:");
    scanf("%d",&n);
    printf("\nEnter data:");
    for(i=1;i<=n;i++)
     { scanf("%d",&x);
       p=(node*)malloc(sizeof(node));
       p->data=x;
       p->next=NULL;
       if(head==NULL || x<head->data)
 { p->next=head;
   head=p;
 }
       else
{ q=head;
 while(q->next !=NULL && x>q->next->data)
   q=q->next;
 p->next=q->next;
 q->next=p;
}
     }
   return(head);
 }
 void print(node *head)
  {
printf("\n");
while(head != NULL)
 {
printf("%5d",head->data);
head=head->next;
 }
  }
void sort(node *head)
  {
    int i,j,n,temp;
    node *p;
   /*counting number of nodes*/
    for(n=0,p=head;p!=NULL;p=p->next)
       n++;
    for(i=1;i<n;i++)
     {
p=head;
for(j=0;j<n-i;j++)
 {
if(p->data > p->next->data)
 {
temp=p->data;
p->data=p->next->data;
p->next->data=temp;
 }
p=p->next;
 }
     }
 }

No comments:

Post a Comment