C++ solution uses minHeap, easy to understand


  • 0
    L

    time complexity O(nlogk)
    space comlexity O(k)

    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            ListNode head(-1);
            vector<ListNode *> heap;
            
            for (int i = 0; i < lists.size(); i++) {
                if (lists[i] != NULL) {
                    heap.push_back(lists[i]);
                    push_heap(heap.begin(), heap.end(), comp);
                }
            }
            
            ListNode *tail = &head;
            while (!heap.empty()) {
                pop_heap(heap.begin(), heap.end(), comp);
                ListNode *t = heap.back();
                heap.pop_back();
                
                if (t->next) {
                    heap.push_back(t->next);
                    push_heap(heap.begin(), heap.end(), comp);
                }
                
                t->next = tail->next;
                tail->next = t;
                tail = t;
            }
            
            return head.next;
        }
    private:
        static bool comp(const ListNode* a, const ListNode* b) {
            if (a->val < b->val)
                return false;
            else
                return true;
        }
    };

  • 0
    E

    why the complexity is nlogk ? THANKS


  • 0
    L

    Because the heap size is k, so every push_heap's time complexity is logk and the total time complexity is nlogk.


  • 0
    E

    I see your solution is super thanks


Log in to reply
 

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