Merge two ordered linked list

by Arun Vishnu · Published November 28, 2008 · Updated March 28, 2009

Merge two ordered linked list to form a 3rd sorted list using C++

/**************************************************************	
	Author: Arun Vishnu M V
	Web: www.arunmvishnu.com
	Description: Merge two oredered linked list to form a 3rd sorted list using C++.
***************************************************************/
#include<conio.h>   	
#include<iostream.h> 
#include<process.h>  


//   Creating a NODE Structure
struct node
{
   int data;  // data
   struct node *next;  // link to next node and previous node
};

// Creating a class LIST
class list
{
   struct node *start;
   public:
      void create(); // to create a list
      void show();   // show
      void merge(list,list);  // Merge two list's
};

// Main function
int main()
{
   clrscr();
   list l1,l2,l3;
   cout<<"Enter the First List in ascending order.\n";
   l1.create(); // to create a first list
   cout<<"\nEnter the Second List in ascending order.\n";
   l2.create(); // to create a second list
   cout<<"\nThe first list is\n";
   l1.show();
   cout<<"\nThe second list is\n";
   l2.show();
   l3.merge(l1,l2);
   l3.show();
   getch();
   return (0);
}

//    Functions

// Creating a new node
void list::create()
{
   struct node *nxt_node,*pre_node;
   int value,no,i;
   start=nxt_node=pre_node=NULL;
   cout<<"\nHow many nodes : ";
   cin>>no;
   cout<<"Enter "<>value;
      nxt_node=new node;
      nxt_node->data=value;
      nxt_node->next=NULL;
      if(start==NULL)
	 start=nxt_node;
      else
	 pre_node->next=nxt_node;
      pre_node=nxt_node;
   }
   cout<<"\nThe list is created!\n\n";
}

// Displaying LIST
void list::show()
{
   struct node *ptr=start;
   cout<<"\n\nThe List is \n";
   while(ptr!=NULL)
   {
      cout<data<<" -> ";
      ptr=ptr->next;
   }
   cout<<"\b\b\b   ";
}

void list::merge(list l1,list l2)
{
   struct node *nxt_node,*pre_node,*pptr,*qptr;
   int dat;
   pptr=l1.start;
   qptr=l2.start;
   start=nxt_node=pre_node=NULL;
   while(pptr!=NULL && qptr!=NULL)
   {
      if(pptr->data<=qptr->data)
      {
	 dat=pptr->data;
	 pptr=pptr->next;
      }
      else
      {
	 dat=qptr->data;
	 qptr=qptr->next;
      }
      nxt_node=new node;
      nxt_node->data=dat;
      nxt_node->next=NULL;
      if(start==NULL)
	 start=nxt_node;
      else
	 pre_node->next=nxt_node;
      pre_node=nxt_node;
   }
   if(pptr==NULL)
   {
      while(qptr!=NULL)
      {
	 nxt_node=new node;
	 nxt_node->data=qptr->data;
	 nxt_node->next=NULL;
	 if(start==NULL)
	    start=nxt_node;
	 else
	    pre_node->next=nxt_node;
	 pre_node=nxt_node;
	 qptr=qptr->next;
      }
   }
   else if(qptr==NULL)
   {
      while(pptr!=NULL)
      {
	 nxt_node=new node;
	 nxt_node->data=pptr->data;
	 nxt_node->next=NULL;
	 if(start==NULL)
	    start=nxt_node;
	 else
	    pre_node->next=nxt_node;
	 pre_node=nxt_node;
	 pptr=pptr->next;
      }
   }
   cout<<"\nThe lists are merged.";
   return;
}
//---------------------- END--------------------