Merge Two Sorted Lists Problem
Description
LeetCode Problem 21. Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
Example:
1
2
3
4
5
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,5]
Input: l1 = [], l2 = []
Output: []
Solution
The solution to this problem is straightforward. The idea is to compare the nodes from the two lists, and add the smaller node to the new list each time.
First, we set up a head list node to allow us to easily return the head of the merged list later. We also use three pointers currNode, currNode1, and currNode2 to keep track of the current node in the merged list, list 1, and list 2, respectively.
Then we do the following steps until either list 1 or list 2 is empty. If the value of currNode1 is less than or equal to currNode2, we point currNode’s next pointer to currNode1, and point currNode1 to its next node. If the value of currNode2 is less than currNode1, we point currNode’s next pointer to currNode2, and point currNode2 to its next node.
After these steps, at most one of list 1 and list 2 is non-empty. We can point currNode to the non-empty list’s rest elements and return the head node.
The time complexity is O(n+m), where n and m are the length of the lists. The space complexity is O(1).
Sample C++ Code
This is a C++ implementation of the above approach.
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
#include <iostream>
#include <algorithm>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL)
return l2;
if (l2 == NULL)
return l1;
ListNode* currNode1 = l1;
ListNode* currNode2 = l2;
ListNode* currNode;
ListNode* head;
currNode1 = l1;
currNode2 = l2;
if (l1->val <= l2->val) {
head = l1;
currNode = l1;
currNode1 = currNode1->next;
}
else {
head = l2;
currNode = l2;
currNode2 = currNode2->next;
}
while ((currNode1 != NULL) && (currNode2 != NULL)) {
if (currNode1->val <= currNode2->val) {
currNode->next = currNode1;
currNode1 = currNode1->next;
currNode = currNode->next;
} else {
currNode->next = currNode2;
currNode2 = currNode2->next;
currNode = currNode->next;
}
}
if (currNode1 == NULL) {
currNode->next = currNode2;
} else {
currNode->next = currNode1;
}
return head;
}
int main() {
ListNode* l1 = new ListNode(1);
l1->next = new ListNode(2);
l1->next->next = new ListNode(4);
ListNode* l2 = new ListNode(1);
l2->next = new ListNode(3);
l2->next->next = new ListNode(4);
ListNode* head = mergeTwoLists(l1, l2);
while (head != nullptr) {
cout << head->val << " ";
head = head->next;
}
return 0;
}