首先实现一个归并函数merge(),然后将lists中的链表两两合并。如果lists中的链表数量为偶数n，那么合并后数量为n/2，否则为n/2+1。当合并成一个链表的时候，退出循环并返回该链表。全程lists数组被复用。
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size()==0) return NULL;
int n = lists.size();
while(n>1){
for(int i = 0;i<n/2;i++){
lists[i] = merge(lists[2*i],lists[2*i+1]);
}
if(n%2==1) {
lists[n/2]=lists[n-1];
n = n/2+1;
}else
n = n/2;
}
return lists[0];
}
ListNode * merge(ListNode *left,ListNode *right){
ListNode * res = new ListNode(-1);
ListNode *p = res;
while(left&&right){
if(left->val<=right->val){
p->next=left;
left=left->next;
}else{
p->next = right;
right = right->next;
}
p = p->next;
}
if(left) p->next = left;
if(right) p->next = right;
return res->next;
}
};
