# Merge two sorted Linked Lists

Here we will write a function merge(list 1, list 2) which will take two sorted linked list as argument and it will merge them to form a new linked list in ascending order.

For example we will have two linked lists 2 -> 5 -> 9 and  3 -> 7 -> 11 and the function will create third linked list as 2 -> 3 -> 5 -> 7 -> 9 -> 11.

Let’s see the code.

## Program to Merge two sorted Linked Lists in C++

```#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: n";
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;
}

// 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 "<<no<<" Elements: ";
for(i=1;i<=no;i++)
{
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<<"n The list is created!";
}

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

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<<"   The lists are merged.";
return;
}```

## Sample Output:

```Enter the First List in ascending order:

How many nodes: 5
Enter 5 Elements: 2
4
8
12
22

The list is created!
Enter the Second List in ascending order:
How many nodes: 5
Enter 5 Elements: 3
7
9
18
23

The list is created!
The first list is:
The List is 2 -> 4 -> 8 -> 12 -> 22
The second list is:
The List is 3 -> 7 -> 9 -> 18 -> 23     The lists are merged.
The List is 2 -> 3 -> 4 -> 7 -> 8 -> 9 -> 12 -> 18 -> 22 -> 23```