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


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

1
2
3

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

Merge linked list

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

Related: 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

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;
}


C++ Implementation to Merge Sorted Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173

#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
Split Singly Circular Linked List
Doubly Circular Linked List
Reverse the Linked List [Finding Length of Loop in Linked List
Doubly Linked List
Singly Linked List