Name: Merge Two Sorted Lists
Difficulty: Easy
Description: Merge two linked lists in sorted order
Example:
Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4] Input: list1 = [], list2 = [] Output: [] Input: list1 = [], list2 = [0] Output: [0]
The excellent STL does all the hard work. I push the numbers from the two lists into a vector, sort the vector, then return a new linked list populated with the sorted items.
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr && list2 == nullptr) return nullptr;
vector<int> numbers;
for(auto i = list1; i != nullptr; i = i->next) {
numbers.push_back(i->val);
}
for(auto i = list2; i != nullptr; i = i->next) {
numbers.push_back(i->val);
}
sort(numbers.begin(), numbers.end());
auto result = new ListNode(numbers.front());
auto previous = result;
for(auto i = numbers.begin() + 1; i < numbers.end(); ++i) {
previous = previous->next = new ListNode(*i);
}
return result;
}