A solution with heap.


  • 1
    J

    Just a conventional solution(420ms)

    class Solution {
    public:
        static bool cmp( ListNode*& a,  ListNode*& b)
        {
            return (b->val-a->val)<0;
        }
        
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            //remove the empty List
            for(vector<ListNode*>::iterator it=lists.begin();it!=lists.end(); ){
                if(*it==NULL){
                    lists.erase(it);
                }else{
                    it++;
                }
            }
            
            ListNode* head = NULL;
            ListNode* index= NULL;
            ListNode* temp = NULL;
            //heap
            std::make_heap (lists.begin(),lists.end(),cmp);
            
            while(true){
                if(lists.size()<=0){
                    break;
                }
                //pick the smallest one 
                std::pop_heap(lists.begin(),lists.end(),cmp);
                temp=lists.back();
                lists.pop_back();
                
                if(head == NULL){
                    head = temp;
                    index = head;
                }else{
                    index->next=temp;
                    index = temp;
                }
                //if has more,add to heap
                if(temp->next!=NULL){
                    temp=temp->next;
                    lists.push_back(temp);
                    std::push_heap(lists.begin(), lists.end(), cmp);
                }
            }
            return head;
        }
    };

Log in to reply
 

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