Straightforward solution using priority queue


  • 0
    O
    struct Compare
    {
        bool operator()(const ListNode* a, const ListNode* b)
        {
            return (a->val > b->val);
        }
    };
    
    
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        if(lists.empty())
            return NULL;
        
        ListNode* safeGuard = new ListNode(-1);
        ListNode* iter = safeGuard;
        priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
        
        for(int i=0; i<lists.size(); i++)
        {
            if(lists[i] != NULL)
                pq.push(lists[i]);
        }
        
        while(!pq.empty())
        {
            ListNode* tmp = pq.top();
            pq.pop();
            iter->next = tmp;
            tmp = tmp->next;
            iter = iter->next;
            iter->next = NULL;
            if(tmp!=NULL)
                pq.push(tmp);
        }
        
        iter = safeGuard->next;
        delete safeGuard;
        safeGuard = NULL;
        return iter;
    }

Log in to reply
 

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