思路是用一个优先队列，给它自定义一个排序函数即可。
/*链表结点的定义(请不要在代码中定义该类型)
struct ListNode {
int val;
ListNode *next;
};
*/
//lists包含k个链表的头结点,返回合并后链表头结点
const int INT_MAX=2147483647;
class compare
{
public:
bool operator()(ListNode* n1,ListNode* n2)const
{
if ( !n1 || !n2)
return !n1;
return n1->val>n2->val;
}
};
ListNode* merge(vector<ListNode*> &lists) {
if ( lists.empty() )
return NULL;
ListNode guard;
ListNode* tail=&guard;
priority_queue<ListNode*,vector<ListNode*>,compare> Q;
for(int i=0;i<lists.size();i++)
Q.push(lists[i]);
while(!Q.empty()&&Q.top()!=NULL)
{
ListNode* t=Q.top();
Q.pop();
tail->next=t;
tail=tail->next;
Q.push(t->next);
}
return guard.next;
}