Merge Two Sorted Lists
In this page:
Problem
Given two linked lists that are each already sorted, they can be combined into a single sorted list without fully re-sorting anything, by repeatedly picking off the smaller of the two current front values.
Example: Problem
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* l1 = new Node{1, new Node{3, new Node{5, nullptr}}};
Node* l2 = new Node{2, new Node{4, nullptr}};
cout << "list1: 1 3 5, list2: 2 4 -- both already sorted" << endl;
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node l1 = new Node(1); l1.next = new Node(3); l1.next.next = new Node(5);
Node l2 = new Node(2); l2.next = new Node(4);
System.out.println("list1: 1 3 5, list2: 2 4 -- both already sorted");
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
l1 = Node(1); l1.next = Node(3); l1.next.next = Node(5)
l2 = Node(2); l2.next = Node(4)
print("list1: 1 3 5, list2: 2 4 -- both already sorted")#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *l1 = malloc(sizeof(struct Node)); l1->data = 1;
l1->next = malloc(sizeof(struct Node)); l1->next->data = 3;
l1->next->next = malloc(sizeof(struct Node)); l1->next->next->data = 5; l1->next->next->next = NULL;
printf("list1: 1 3 5 -- already sorted\n");
return 0;
}Login to try C/C++/Java code in the editor
Merge Process
At each step, compare the current node of both lists and attach whichever one holds the smaller value to the result, then advance only that list's pointer forward to its next node.
Example: Merge Process
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* l1 = new Node{1, new Node{3, nullptr}};
Node* l2 = new Node{2, new Node{4, nullptr}};
Node dummy{0, nullptr}; Node* tail = &dummy;
while (l1 && l2) {
if (l1->data < l2->data) { tail->next = l1; l1 = l1->next; }
else { tail->next = l2; l2 = l2->next; }
tail = tail->next;
}
for (Node* c = dummy.next; c; c = c->next) cout << c->data << " ";
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node l1 = new Node(1); l1.next = new Node(3);
Node l2 = new Node(2); l2.next = new Node(4);
Node dummy = new Node(0); Node tail = dummy;
while (l1 != null && l2 != null) {
if (l1.data < l2.data) { tail.next = l1; l1 = l1.next; }
else { tail.next = l2; l2 = l2.next; }
tail = tail.next;
}
for (Node c = dummy.next; c != null; c = c.next) System.out.print(c.data + " ");
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
l1 = Node(1); l1.next = Node(3)
l2 = Node(2); l2.next = Node(4)
dummy = Node(0)
tail = dummy
while l1 and l2:
if l1.data < l2.data:
tail.next = l1; l1 = l1.next
else:
tail.next = l2; l2 = l2.next
tail = tail.next
c = dummy.next
while c:
print(c.data, end=" ")
c = c.next#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *l1 = malloc(sizeof(struct Node)); l1->data = 1;
l1->next = malloc(sizeof(struct Node)); l1->next->data = 3; l1->next->next = NULL;
struct Node *l2 = malloc(sizeof(struct Node)); l2->data = 2;
l2->next = malloc(sizeof(struct Node)); l2->next->data = 4; l2->next->next = NULL;
struct Node dummy = {0, NULL}; struct Node *tail = &dummy;
while (l1 && l2) {
if (l1->data < l2->data) { tail->next = l1; l1 = l1->next; }
else { tail->next = l2; l2 = l2->next; }
tail = tail->next;
}
for (struct Node *c = dummy.next; c; c = c->next) printf("%d ", c->data);
return 0;
}Login to try C/C++/Java code in the editor
Remaining Nodes
Once one of the two lists runs out of nodes, there's no need to keep comparing: the remainder of the other list is already sorted, so it can simply be attached wholesale to the end of the result.
Example: Remaining Nodes
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* l1 = nullptr;
Node* l2 = new Node{2, new Node{4, new Node{6, nullptr}}};
Node dummy{0, nullptr}; Node* tail = &dummy;
tail->next = l1 ? l1 : l2;
cout << "list1 exhausted, remainder of list2 attached wholesale: ";
for (Node* c = tail->next; c; c = c->next) cout << c->data << " ";
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node l1 = null;
Node l2 = new Node(2); l2.next = new Node(4); l2.next.next = new Node(6);
Node dummy = new Node(0);
dummy.next = (l1 != null) ? l1 : l2;
System.out.print("list1 exhausted, remainder of list2 attached wholesale: ");
for (Node c = dummy.next; c != null; c = c.next) System.out.print(c.data + " ");
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
l1 = None
l2 = Node(2); l2.next = Node(4); l2.next.next = Node(6)
dummy = Node(0)
dummy.next = l1 if l1 else l2
print("list1 exhausted, remainder of list2 attached wholesale: ", end="")
c = dummy.next
while c:
print(c.data, end=" ")
c = c.next#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *l1 = NULL;
struct Node *l2 = malloc(sizeof(struct Node)); l2->data = 2;
l2->next = malloc(sizeof(struct Node)); l2->next->data = 4; l2->next->next = NULL;
struct Node dummy = {0, NULL};
dummy.next = l1 ? l1 : l2;
printf("remainder attached wholesale: ");
for (struct Node *c = dummy.next; c; c = c->next) printf("%d ", c->data);
return 0;
}Login to try C/C++/Java code in the editor
Result
Because every original node is reused in the merged result rather than copied, and the smaller of the two current values is chosen at each step, the final list is guaranteed to remain fully sorted throughout.
Example: Result
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
Node* merge(Node* l1, Node* l2) {
Node dummy{0, nullptr}; Node* tail = &dummy;
while (l1 && l2) {
if (l1->data < l2->data) { tail->next = l1; l1 = l1->next; }
else { tail->next = l2; l2 = l2->next; }
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
int main() {
Node* l1 = new Node{1, new Node{4, nullptr}};
Node* l2 = new Node{2, new Node{3, nullptr}};
for (Node* c = merge(l1, l2); c; c = c->next) cout << c->data << " ";
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
static Node merge(Node l1, Node l2) {
Node dummy = new Node(0); Node tail = dummy;
while (l1 != null && l2 != null) {
if (l1.data < l2.data) { tail.next = l1; l1 = l1.next; }
else { tail.next = l2; l2 = l2.next; }
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
public static void main(String[] args) {
Node l1 = new Node(1); l1.next = new Node(4);
Node l2 = new Node(2); l2.next = new Node(3);
for (Node c = merge(l1, l2); c != null; c = c.next) System.out.print(c.data + " ");
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
def merge(l1, l2):
dummy = Node(0)
tail = dummy
while l1 and l2:
if l1.data < l2.data:
tail.next = l1; l1 = l1.next
else:
tail.next = l2; l2 = l2.next
tail = tail.next
tail.next = l1 if l1 else l2
return dummy.next
l1 = Node(1); l1.next = Node(4)
l2 = Node(2); l2.next = Node(3)
c = merge(l1, l2)
while c:
print(c.data, end=" ")
c = c.next#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
struct Node* merge(struct Node *l1, struct Node *l2) {
struct Node dummy = {0, NULL}; struct Node *tail = &dummy;
while (l1 && l2) {
if (l1->data < l2->data) { tail->next = l1; l1 = l1->next; }
else { tail->next = l2; l2 = l2->next; }
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
int main() {
struct Node *l1 = malloc(sizeof(struct Node)); l1->data = 1;
l1->next = malloc(sizeof(struct Node)); l1->next->data = 4; l1->next->next = NULL;
struct Node *l2 = malloc(sizeof(struct Node)); l2->data = 2;
l2->next = malloc(sizeof(struct Node)); l2->next->data = 3; l2->next->next = NULL;
for (struct Node *c = merge(l1, l2); c; c = c->next) printf("%d ", c->data);
return 0;
}Login to try C/C++/Java code in the editor
Complexity
Merging finishes in O(n+m) time, visiting each node of both lists exactly once, and needs only O(1) extra space beyond the input lists themselves, since it just relinks existing nodes instead of allocating new ones.
Example: Complexity
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
Node* merge(Node* l1, Node* l2) {
Node dummy{0, nullptr}; Node* tail = &dummy;
while (l1 && l2) {
if (l1->data < l2->data) { tail->next = l1; l1 = l1->next; }
else { tail->next = l2; l2 = l2->next; }
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
int main() {
Node* l1 = new Node{1, new Node{4, nullptr}};
Node* l2 = new Node{2, new Node{3, nullptr}};
merge(l1, l2);
cout << "O(n+m) time, O(1) space -- nodes relinked, not copied" << endl;
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
static Node merge(Node l1, Node l2) {
Node dummy = new Node(0); Node tail = dummy;
while (l1 != null && l2 != null) {
if (l1.data < l2.data) { tail.next = l1; l1 = l1.next; }
else { tail.next = l2; l2 = l2.next; }
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
public static void main(String[] args) {
Node l1 = new Node(1); l1.next = new Node(4);
Node l2 = new Node(2); l2.next = new Node(3);
merge(l1, l2);
System.out.println("O(n+m) time, O(1) space -- nodes relinked, not copied");
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
def merge(l1, l2):
dummy = Node(0)
tail = dummy
while l1 and l2:
if l1.data < l2.data:
tail.next = l1; l1 = l1.next
else:
tail.next = l2; l2 = l2.next
tail = tail.next
tail.next = l1 if l1 else l2
return dummy.next
l1 = Node(1); l1.next = Node(4)
l2 = Node(2); l2.next = Node(3)
merge(l1, l2)
print("O(n+m) time, O(1) space -- nodes relinked, not copied")#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
struct Node* merge(struct Node *l1, struct Node *l2) {
struct Node dummy = {0, NULL}; struct Node *tail = &dummy;
while (l1 && l2) {
if (l1->data < l2->data) { tail->next = l1; l1 = l1->next; }
else { tail->next = l2; l2 = l2->next; }
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
int main() {
struct Node *l1 = malloc(sizeof(struct Node)); l1->data = 1;
l1->next = malloc(sizeof(struct Node)); l1->next->data = 4; l1->next->next = NULL;
struct Node *l2 = malloc(sizeof(struct Node)); l2->data = 2;
l2->next = malloc(sizeof(struct Node)); l2->next->data = 3; l2->next->next = NULL;
merge(l1, l2);
printf("O(n+m) time, O(1) space\n");
return 0;
}Login to try C/C++/Java code in the editor
🔒
Chapter Quiz — Complete all 8 topics to unlock
0/8 topics done
Complete these topics first: