Merge Two Sorted Linked Lists

Write a C++ Program to Merge Two Sorted Linked Lists To Form Third Linked List. Here’s simple Program to Merge Two Sorted Linked Lists To Form Third Linked List in C++ Programming Language.

Below is the source code for C++ Program to Merge Two Sorted Linked Lists To Form Third Linked List which is successfully compiled and run on Windows System to produce desired output as shown below :

SOURCE CODE : :

/*  C++ Program to Merge Two Sorted Linked Lists To Form Third Linked List  */

#include<iostream>

using namespace std;

//   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()
{
   list l1,l2,l3;
   cout<<"\nEnter the First List in ascending order :: ";
   l1.create(); // to create a first list
   cout<<"\nEnter the Second List in ascending order :: ";
   l2.create(); // to create a second list
   cout<<"\nThe first list is :: ";
   l1.show();
   cout<<"\nThe second list is :: ";
   l2.show();
   l3.merge(l1,l2);
   l3.show();
   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<<"\nEnter "<<no<<" Elements :: ";
   for(i=1;i<=no;i++)
   {
       cout<<"\nEnter [ "<<i<<" ] Element :: ";
      cin>>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";
}

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

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.......\n";
   return;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

/* C++ Program to Merge Two Sorted Linked Lists To Form Third Linked List */

#include<iostream>

using namespace std;

// 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()

{

list l1,l2,l3;

cout<<"\nEnter the First List in ascending order :: ";

l1.create(); // to create a first list

cout<<"\nEnter the Second List in ascending order :: ";

l2.create(); // to create a second list

cout<<"\nThe first list is :: ";

l1.show();

cout<<"\nThe second list is :: ";

l2.show();

l3.merge(l1,l2);

l3.show();

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<<"\nEnter "<<no<<" Elements :: ";

for(i=1;i<=no;i++)

{

cout<<"\nEnter [ "<<i<<" ] Element :: ";

cin>>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";

}

// Displaying LIST

void list::show()

{

struct node *ptr=start;

cout<<"\nThe List is :: ";

while(ptr!=NULL)

{

cout<<ptr->data<<" -> ";

ptr=ptr->next;

}

cout<<"\n";

}

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.......\n";

return;

}

OUTPUT : :

/* C++ Program to Merge Two Sorted Linked Lists  */

Enter the First List in ascending order ::
How many nodes :: 5

Enter 5 Elements ::
Enter [ 1 ] Element :: 1

Enter [ 2 ] Element :: 2

Enter [ 3 ] Element :: 3

Enter [ 4 ] Element :: 4

Enter [ 5 ] Element :: 5

The list is created!

Enter the Second List in ascending order ::
How many nodes :: 3

Enter 3 Elements ::
Enter [ 1 ] Element :: 1

Enter [ 2 ] Element :: 2

Enter [ 3 ] Element :: 3

The list is created!

The first list is ::
The List is :: 1 -> 2 -> 3 -> 4 -> 5 ->

The second list is ::
The List is :: 1 -> 2 -> 3 ->

The lists are merged.......

The List is :: 1 -> 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 5 ->

Process returned 0

/* C++ Program to Merge Two Sorted Linked Lists */

Enter the First List in ascending order ::

How many nodes :: 5

Enter 5 Elements ::

Enter [ 1 ] Element :: 1

Enter [ 2 ] Element :: 2

Enter [ 3 ] Element :: 3

Enter [ 4 ] Element :: 4

Enter [ 5 ] Element :: 5

The list is created!

Enter the Second List in ascending order ::

How many nodes :: 3

Enter 3 Elements ::

Enter [ 1 ] Element :: 1

Enter [ 2 ] Element :: 2

Enter [ 3 ] Element :: 3

The list is created!

The first list is ::

The List is :: 1 -> 2 -> 3 -> 4 -> 5 ->

The second list is ::

The List is :: 1 -> 2 -> 3 ->

The lists are merged.......

The List is :: 1 -> 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 5 ->

Process returned 0

Above is the source code and output for C++ Program to Merge Two Sorted Linked List To Form Third Linked List which is successfully compiled and run on Windows System to produce desired output.

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach upto you in the short interval.

Thanks for reading the post….

0 0 vote

Article Rating