首先實(shí)現(xiàn)一個(gè)歸并函數(shù)merge(),然后將lists中的鏈表兩兩合并蛾扇。如果lists中的鏈表數(shù)量為偶數(shù)n攘烛，那么合并后數(shù)量為n/2，否則為n/2+1镀首。當(dāng)合并成一個(gè)鏈表的時(shí)候坟漱，退出循環(huán)并返回該鏈表。全程lists數(shù)組被復(fù)用更哄。
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;
}
};
