合并k个顺序链表

---

image.png

先每个链表读首位元素，优先队列pop的时候删除对应链表首位元素然后修改list指针，将新首位元素放入优先队列中，如果新首位元素是NULL注意要跳过。直到最后优先队列为空。

• 如何获取优先队列中元素对应的list行数？ 用pair容器装<List*,int行数>即可。

class Solution {
public:
    struct cmp{
        bool operator()(pair<ListNode*,int>a,pair<ListNode*,int>b){
            return (a.first)->val>(b.first)->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0){
            return NULL;
        }
        ListNode * res=NULL;
        ListNode * ends=NULL;
        priority_queue<pair<ListNode*,int>,vector<pair<ListNode*,int>>,cmp>pq;
        int i=0;
        for(i=0;i<lists.size();i++){
            if(lists[i]!=NULL){
                pq.push(make_pair(lists[i],i));
            }
        }
        if(pq.size()==0){
            return NULL;
        }
        auto t=pq.top();
        res=t.first;
        ends=res;
        pq.pop();
        lists[t.second]=lists[t.second]->next;
        if(lists[t.second]!=NULL){
            pq.push(make_pair(lists[t.second],t.second));
        }

        while(pq.size()>0){
            auto t=pq.top();
            ends->next=t.first;
            ends=ends->next;
            pq.pop();
            lists[t.second]=lists[t.second]->next;
            if(lists[t.second]!=NULL){
                pq.push(make_pair(lists[t.second],t.second));
            }
        }
        return res;
    }
};