Leetcode 23. Merge k Sorted Lists

https://leetcode.com/problems/merge-k-sorted-lists/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

#include <queue>
using namespace std;
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        /*
        
        把每一个链表的头指针放到优先队列中，每次选最小的那个,取出后将其下一个指针(不为空)放入优先队列.
        边界:
        1.有些链表开始就为空
        
        */
        struct cmp{
            bool operator() (ListNode *a,ListNode *b){return a->val>b->val;};
        };
        
        ListNode* pre=new ListNode(0),*pp=pre;
        priority_queue<ListNode*,vector<ListNode*>,cmp> que; 
        for(auto& p:lists)
            if(p) que.push(p);
        while(!que.empty()){
            //取最小的
            auto *p=que.top();
            que.pop();
            
            pp->next=p;
            pp=pp->next;
            //加入新的指针
            if(pp->next) que.push(pp->next);
        }
        pp=pre->next;
        delete pre;
        return pp;
        
    }
};

Leetcode 23. Merge k Sorted Lists

原文：https://www.cnblogs.com/ximelon/p/10832798.html