23. Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        multimap<int, ListNode*> m;
        ListNode* dummy = new ListNode();
        for(auto n : lists) {
            if(n) m.insert({n->val, n});
        }
        ListNode* cur = dummy;
        while(m.size() > 1) {
            auto rm = m.begin();
            cur->next = rm->second;
            if(rm->second->next) {
                m.insert({rm->second->next->val, rm->second->next});
            }
            m.erase(rm);
            cur = cur->next;
        }
        cur->next = m.begin()->second;
        return dummy->next;
    }
};