Search This Blog

MergeSort program to merge two linked lists into a third list

 #include<stdio.h>  
 #include<conio.h>  
 #include<stdlib.h>  
 int flag;  
 struct Node  
 {  
      int data;  
      struct Node* next;  
 };  
 typedef struct Node List;  
 List* start1;  
 List* start2;  
 List* start3;  
 List List1,List2,List3;  
 List* getNode()  
 {  
      return ((List*)malloc(sizeof(List)));  
 }  
 void showList(List* s)  
 {  
      List* p=s;  
      printf("\n List contains:");  
      if(p==NULL)  
      {  
           printf("SORRY. NO ELEMENTS ,LIST IS EMPTY\n");  
           return;  
      }  
      while(p->next!=NULL)  
      {  
           printf(" %d ",p->data);  
           p=p->next;  
      }  
      printf(" %d\n",p->data);  
 }  
 void sort(List* s)  
 {  
      List* w=NULL;  
      List* y=s;  
      int temp;  
  if(s==NULL)  
  {  
       printf("\n Empty linked list\n");  
       return;  
  }       
 while(y->next!=NULL)  
 {  
      w=s;  
      while(w->next!=NULL)  
      {  
       if((w->data) > (w->next->data))  
       {  
           temp=w->data;  
     w->data=w->next->data;  
     w->next->data=temp;            
       }       
    w=w->next;        
      }  
      y=y->next;  
 }       
 }  
 void push(int data)  
 {  
      List* q=getNode();  
      List* p=NULL;  
      if(flag==0)  
           p=start1;  
      else  
           p=start2;  
      q->next=NULL;  
      q->data=data;  
      if(p==NULL)  
      {  
           if(flag==0)  
           start1=q;  
        else  
                start2=q;  
           return;  
      }  
      while(p->next!=NULL)  
      {  
           p=p->next;  
      }  
      p->next=q;  
 }  
 void mergeLists()  
 {   int data;  
      List* s1=start1;  
      List* s2=start2;  
      List* s3=start3;  
      List* q=NULL;  
      List* p=NULL;  
      while(s1!=NULL && s2!=NULL)  
      {  q=getNode();  
           if(s1->data < s2->data)  
           {  
                q->data=s1->data;  
                if(start3==NULL)  
                     start3=q;  
                else  
                {  
                 p=start3;  
                 while(p->next!=NULL)  
                      p=p->next;  
                 p->next=q;  
                 q->next=NULL;  
                }  
                s1=s1->next;  
           }  
           else  
           {  
                q->data=s2->data;  
                if(start3==NULL)  
                     start3=q;  
                else  
                {  
                     p=start3;  
                     while(p->next!=NULL)  
                          p=p->next;  
                     p->next=q;  
                     q->next=NULL;  
                }  
                s2=s2->next;  
           }  
      }  
           while(s1!=NULL)  
           {  
                p=start3;  
                q=getNode();  
                q->data=s1->data;  
                while(p->next!=NULL)  
                     p=p->next;  
                p->next=q;  
                q->next=NULL;  
                s1=s1->next;  
           }  
           while(s2!=NULL)  
           {  
                p=start3;  
                q=getNode();  
                q->data=s2->data;  
                while(p->next!=NULL)  
                     p=p->next;  
                p->next=q;  
                q->next=NULL;  
                s2=s2->next;  
           }  
      while(start1!=NULL)  
      {  
           p=start1;  
           start1=start1->next;  
           free(p);       
      }  
      while(start2!=NULL)  
      {  
           p=start2;  
           start2=start2->next;  
           free(p);       
      }  
 }  
 void main()  
 {  
      int option,data;  
      do{  
      start1=NULL;  
      start2=NULL;  
      start3=NULL;  
      flag=0;  
      clrscr();  
      printf("\n****ENTER LIST1 ELEMENTS****\n");  
      while(1)  
      {  
           printf("\nEnter data:");scanf("%d",&data);  
           push(data);  
           printf("Enter 1 to CONTINUE or 3 to EXIT LIST1 ...");scanf("%d",&option);  
           if(option==3)  
                break;  
      }  
      sort(start1);  
      printf("\n****SORTED LIST1 ELEMENTS****");  
      showList(start1);  
      flag=1;  
      printf("\n****ENTER LIST2 ELEMENTS****\n");  
      while(1)  
      {  
           printf("\nEnter data:");scanf("%d",&data);  
           push(data);  
           printf("Enter 1 to CONTINUE or 3 to EXIT LIST2 ...");scanf("%d",&option);  
           if(option==3)  
                break;  
      }  
      sort(start2);  
      printf("\n\n****SORTED LIST1 ELEMENTS****\n");  
      showList(start1);  
      printf("****SORTED LIST2 ELEMENTS****");  
      showList(start2);printf("MERGING LIST1 AND LIST2 ELEMENTS INTO LIST3 ......");  
      mergeLists();  
      printf("\n****SORTED LIST3 ELEMENTS****");  
      showList(start3);  
      printf("\nENTER 1 to CONTINUE ,or 3 to EXIT :");scanf("%d",&option);  
      }while(option!=3);  
      getch();  
 }  

No comments:

Post a Comment

leave a comment here