Merge two sorted Linked List (in-place) | C++ Implementation

Given two sorted Linked List, we have to merge them without using another linked list.

  List 1 : { 5, 10, 18, 25 }
  List 2 : { 6, 8, 11, 20 }
  Merged List : { 5, 6, 8, 10, 11, 18, 20, 25 }

{:class="img-responsive"}

From the above fig. we can see that merging two linked list is same as merging two sorted array in mergesort.

Related: [Merge Sort]({{ site.url }}//blog/2017/08/24/C++-Implementation-of-Merge-Sort)

node stores the smallest element in both linked list and it will become the head of the merged linked list later.

head1 and head2 are the nodes whose data item is to be compared and node with smallest data item is added after tmp. tmp is always the last node in merged list.

Here is mergeSortedList functions.

void mergeSortedList(LinkedList<T>& ll2)
{
    if(ll2.head == nullptr)
        return;

    if(head == nullptr)
    {
        head = ll2.head;
        ll2.head = nullptr;
        return;
    }

    Node *head1 = head;
    Node *head2 = ll2.head;

    Node *node;

    if(head1->data <= head2->data)
    {
        node = head1;
        advance(head1);
    }
    else if(head2->data <= head1->data)
    {
        node = head2;
        advance(head2);
    }

    Node *tmp = nullptr;
    tmp = node;

    while(head1 != nullptr && head2 != nullptr)
    {
        if(head1->data <= head2->data)
        {
            tmp->next = head1;
            advance(head1);
        }
        else
        {
            tmp->next = head2;
            advance(head2);
        }

        advance(tmp);
    }

    //if there are extra nodes in either list
    if(head1 != nullptr)
        tmp->next = head1;

    if(head2 != nullptr)
        tmp->next = head2;

    head = node;
        ll2.head = nullptr;
}

{% include ads.html %}

C++ Implementation to Merge Sorted Linked List

#include <iostream>
#include <utility>
#include <cassert>

template<class T>
class LinkedList
{
    struct Node
    {
        T data;
        Node * next = nullptr;
        Node()          : data(), next(nullptr) {}
        Node(T value)   : data(std::move(value)), next(nullptr) {}
    };

    Node *head;

  public:
    LinkedList() : head(nullptr) {}
    LinkedList(const LinkedList& ll) = delete; //copy constructor
    LinkedList& operator=(const LinkedList& ll) = delete; //copy assignment
    ~LinkedList()
    {
        Node *tmp = nullptr;
        while(head)
        {
            tmp = head;
            head = head->next;
            delete tmp;
        }
        head = nullptr;
    }

    void insert(T);
    void mergeSortedList(LinkedList<T>&);
    void printList() const;

  private:
    static void advance(Node*& node)
    {
        assert(node != nullptr);
        node = node->next;
    }

    Node* getLastNode(Node*& node)
    {
        while(node->next != nullptr)
        node = node->next;

        return node;
    }
};

template <class T>
void LinkedList<T>::insert(T value)
{
    Node *node = new Node(std::move(value));
    Node *tmp = head;
    if(tmp == nullptr)
    {
        head = node;
    }
    else
    {
        tmp = getLastNode(tmp);
        tmp->next = node;
    }
}

template <class T>
void LinkedList<T>::mergeSortedList(LinkedList<T>& ll2)
{
    if(ll2.head == nullptr)
        return;

    if(head == nullptr)
    {
        head = ll2.head;
        ll2.head = nullptr;
        return;
    }

    Node *head1 = head;
    Node *head2 = ll2.head;

    Node *node;

    if(head1->data <= head2->data)
    {
        node = head1;
        advance(head1);
    }
    else if(head2->data <= head1->data)
    {
        node = head2;
        advance(head2);
    }

    Node *tmp = nullptr;
    tmp = node;

    while(head1 != nullptr && head2 != nullptr)
    {
        if(head1->data <= head2->data)
        {
            tmp->next = head1;
            advance(head1);
        }
        else
        {
            tmp->next = head2;
            advance(head2);
        }

        advance(tmp);
    }

    //if there are extra nodes in either list
    if(head1 != nullptr)
        tmp->next = head1;

    if(head2 != nullptr)
        tmp->next = head2;

    head = node;
        ll2.head = nullptr;
}

template <class T>
void LinkedList<T>::printList() const
{
    if(head == nullptr)
    {
        std::cout << "Empty List \n";
        return;
    }

    Node *node = head;

    while(node != nullptr)
    {
        std::cout << node->data << " ";
        advance(node);
    }

    std::cout << "\n";
}

int main()
{
    LinkedList<int> ll1;
    ll1.insert(5);
    ll1.insert(10);
    ll1.insert(18);
    ll1.insert(25);
    std::cout << "List 1 : ";
    ll1.printList();

    LinkedList<int> ll2;
    ll2.insert(6);
    ll2.insert(8);
    ll2.insert(11);
    ll2.insert(20);
    ll2.insert(23);
    ll2.insert(28);
    ll2.insert(40);
    std::cout << "List 2 : ";
    ll2.printList();

    ll1.mergeSortedList(ll2);
    std::cout << "Merged List : ";
    ll1.printList();
}

View this code on Github

Get this post in pdf - Merge Sorted Linked List

Reference:
Introduction to Algorithms
The Algorithm Design Manual
Data Structures and Algorithms Made Easy

You may also like

[Move all Odd numbers after Even numbers in Singly Linked List]({{ site.url }}/blog/2018/02/08/C++-Move-all-Even-numbers-before-Odd-numbers-in-Singly-Linked-List-(Using-STL))
[Split Singly Circular Linked List]({{ site.url }}/blog/2018/02/04/C++-Split-Singly-Circular-Linked-List-program)
[Doubly Circular Linked List]({{ site.url }}/blog/2018/02/02/C++-Doubly-Circular-Linked-List-program)
[Reverse the Linked List]({{ site.url }}/blog/2018/01/23/C++-Reverse-the-Linked-List-(Iterative-Method)-program) [[Finding Length of Loop in Linked List]({{ site.url }}/blog/2018/01/20/C++-Linked-List-containing-Loop-(Floyd-Cycle-finding-Algorithm)-program)
[Doubly Linked List]({{ site.url }}/blog/2017/07/28/C++-Doubly-Linked-List-using-Template-(Data-Structure))
[Singly Linked List]({{ site.url }}/blog/2017/07/27/C++-Singly-Linked-List-using-Template-(Data-Structure))