leetcode练习题 merge-k-sorted-lists

解题思路

采用优先队列，对优先队列的比较规则进行重载，之后每次从队列中取出值较小的结点，采用尾插法插入新链表中，若该结点还有后续结点，则将后续结点也插入优先队列中参与比较。
知道优先队列为空，返回结果。

代码

#include<queue>
struct compare{bool operator()(const ListNode* l1,const ListNode* l2){return l1->val > l2->val;}
};
class Solution {
public:ListNode *mergeKLists(vector<ListNode *> &lists) {if(lists.size() == 0)return NULL;priority_queue<ListNode *,vector<ListNode *>,compare>q;for(int i = 0;i < lists.size();i++){if(lists[i] != NULL)q.push(lists[i]);}ListNode *first = new ListNode(0);ListNode *tail = first;while(!q.empty()){ListNode *tmp = q.top();q.pop();tail->next = tmp;tail = tail->next;tmp = tmp->next;tail->next = NULL;if(tmp)q.push(tmp);}return first->next;}
};