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