23. 合并K个排序链表

首先实现一个归并函数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;
    }
};