Merge two sorted linked list without any extra space in C++

Hello Friends, Today we are going to learn how to merge two sorted linked lists without any extra space in C++. I hope you know about the linked list and how it stores the data. So I am not going into that. Let’s start with an example and understand how to do this problem and then we will see the code and implementation part.

Example:  Linked list 1  :  4 ->7 -> 12               Linked list 2 :   3 -> 6 ->8 ->11

Output should be :  3 ->4 ->6 -> 7 -> 8 -> 11 -> 12

Let’s see the code now.

C++ code for merging two sorted linked lists

Below is our given program for this task:

#include<iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
    Node(int x)
    {
        data = x;
        next = NULL;
    }
};
Node* sorted(struct Node* a, struct Node* b);
void printlist(struct Node *n)
{
    while (n!=NULL)
    {
        cout << n->data << " ";
        n = n->next;
    }
    cout << endl;
}

int main()
{
        int n,m;
        cin>>n>>m;    // size of two linked list

        // first linked list..... suppose input is 4 7 12

        int data;
        cin>>data;
        struct Node *head1 = new Node(data);  // head pointer
        struct Node *tail1 = head1;
        for (int i = 1; i < n; ++i)         // for loop for taking other node and joining with head pointer
        {
            cin>>data;
            tail1->next = new Node(data);
            tail1 = tail1->next;
        }

      // second linked list  ........     suppose input is 3 6 8 11

        cin>>data;
        struct Node *head2 = new Node(data);
        struct Node *tail2 = head2;
        for(int i=1; i<m; i++)
        {
            cin>>data;
            tail2->next = new Node(data);
            tail2 = tail2->next;
        }

        Node *head = sorted(head1, head2);
        printlist(head);
    
    return 0;
}

Node* sorted(Node* headA, Node* headB)  
{  
    
    struct Node* temp1 = headA;
    struct Node* temp2 = headB;
    struct Node* temp3=NULL,*temp4=NULL;
    if(temp1->data < temp2->data)
    {
        temp4=temp1;
        temp3 = temp4;
        temp1 = temp1->next;
    }
    else
    {
        temp4 = temp2;
        temp3 = temp4;
        temp2 = temp2->next;
    }
    
    while(temp1!=NULL && temp2!=NULL)
    {
        if(temp1->data < temp2->data)
        {
            temp3->next = temp1;
            temp1 = temp1->next;
        }
        else
        {
            temp3->next = temp2;
            temp2 = temp2->next;
        }
        temp3 = temp3->next;
    }
    if(temp1==NULL)
    {
        temp3->next=temp2;
    }
    else if(temp2==NULL)
    {
        temp3->next=temp1;
    }
   return temp4;
}

And the output of the given program will be:

Output : 3 4 6 7 8 11 12

Understanding the Algorithm

The algorithm is quite simple. First, we will compare first node of both the linked list and store in the temp4 node and for rest of the node we will compare and attaching it to the temp4. Then you can return temp4 from the function and printlist function will print the linked list.

You can see other posts also.

• Reverse a linked list using STL stack in C++