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