O(nlogk+klogk) solution / 53 ms


  • 0
    P
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    
    class Compare {
        public:
        bool operator() (ListNode* p, ListNode* q) {
            return p->val > q->val;
        }
    };
    class Solution {
    public:
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
            int n = lists.size();
            // this loop takes O(kLogk) since this is building heap
            for (int i = 0; i < n; ++i) {
                if (lists[i]) {
                    pq.push(lists[i]);
                }
            }
            ListNode* head = new ListNode(INT_MAX);
            ListNode* runner = head;
            while(!pq.empty()) {
                ListNode* top = pq.top();
                pq.pop(); // O(logk)
                runner->next = top;
                if (top->next) {
                    pq.push(top->next); //O(logk)
                }
                runner = runner->next;
                runner->next = NULL;
            }
            return head->next;
        }
    };

  • 0
    X

    For this algorithmn, at least you need do nk times while loop, so I think the run time should be O(nk*(time to pop() + time to push()))


  • 0
    P

    my analysis assumes total n nodes and k lists. So, the analysis is correct, please look carefully.


Log in to reply
 

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