Leetcode 21. How To Merge Two Sorted Linked Lists
Merge two sorted linked lists into a single sorted linked list efficiently using C++.
Problem statement
Given the starting nodes of two sorted linked lists, list1 and list2, your task is to combine these lists into a single sorted linked list.
This merged list should be created by connecting the nodes from both list1 and list2. Finally, you should return the starting node of the resulting merged linked list.
Example 1
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2
Input: list1 = [], list2 = []
Output: []
Example 3
Input: list1 = [], list2 = [0]
Output: [0]
Constraints
- The number of nodes in both lists is in the range
[0, 50]. -100 <= Node.val <= 100.- Both
list1andlist2are sorted in non-decreasing order.
Solution: Constructing a new list
For each pair of nodes between the two lists, pick the node having smaller value to append to the new list.
Code
#include <iostream>
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* list1, ListNode* list2) {
if (list1 == nullptr) {
return list2;
} else if (list2 == nullptr) {
return list1;
}
// identify which list is head of the merged one
ListNode* head = list1;
if (list2->val < head->val) {
head = list2;
list2 = list2->next;
} else {
list1 = list1->next;
}
ListNode* node = head;
while (list1 && list2) {
// pick the smaller node to append to the new list.
if (list1->val < list2->val) {
node->next = list1;
list1 = list1->next;
} else {
node->next = list2;
list2 = list2->next;
}
node = node->next;
}
if (list1 == nullptr) {
node->next = list2;
} else {
node->next = list1;
}
return head;
}
void printResult(ListNode* head) {
std::cout << "[";
while (head) {
std::cout << head->val << ",";
head = head->next;
}
std::cout << "]\n";
}
int main() {
ListNode four1(4);
ListNode two1(2, &four1);
ListNode one1(1, &two1);
ListNode four2(4);
ListNode three2(3, &four2);
ListNode one2(1, &three2);
auto newOne = mergeTwoLists(&one1, &one2);
printResult(newOne);
auto empty = mergeTwoLists(nullptr, nullptr);
printResult(empty);
ListNode zero(0);
auto z = mergeTwoLists(nullptr, &zero);
printResult(z);
}
Output:
[1,1,2,3,4,4,]
[]
[0,]
Complexity
- Runtime:
O(N), whereN = list1.length + list2.length. - Extra space:
O(1).
Conclusion
This solution merges two sorted linked lists efficiently without using extra space.
It identifies the head of the merged list by comparing the values of the first nodes of the input lists. Then, it iterates through both lists, linking nodes in ascending order until one list is exhausted.
Finally, it appends the remaining nodes from the non-empty list to the merged list, ensuring the resulting list remains sorted.
Thanks for reading!
I hope you enjoyed this content. Don't keep it to yourself! Share it with your network and help each other improve your coding skills and advance your career!
Nhut Nguyen, the author of The Problem Solver's Guide To Coding.