C++ Solution using heap


  • 0
    U

    Really straight-forward to use a k-sized heap to solve this problem. You can also use divide and conquer based on merge two sorted lists of course.

    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            int k = lists.size();
            if (!k) return NULL;
            auto cmp = [](pair<int, int> p1, pair<int, int> p2) {return p1.first > p2.first;};
            priority_queue<pair<int, int>, std::vector<pair<int, int>>, decltype(cmp)> q(cmp);
            ListNode* head = new ListNode(-1);
            ListNode* tmp = head;
            for (int i = 0; i < k; i++)
                if (lists[i])
                    q.push(make_pair(lists[i]->val, i));
            
            while (q.size()) {
                int ind = q.top().second;
                tmp->next = lists[ind];
                lists[ind] = lists[ind]->next;
                tmp = tmp->next;
                q.pop();
                if (lists[ind])
                    q.push(make_pair(lists[ind]->val, ind));
            }
            
            return head->next;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.