题解 | #合并k个已排序的链表#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  	//返回两个有序链表合成的有序列表
    ListNode *sort(ListNode* list1,ListNode* list2){
        if(!list1)
            return list2;
        if(!list2)
            return list1;
        ListNode *newHead= new ListNode(0);
        ListNode* newTail, *tmp;
        newTail = newHead;
        while(list1 && list2){
            if(list1->val<list2->val){
                tmp = list1->next;
                list1->next = NULL;
                newTail->next = list1;
                newTail = list1;
                list1 = tmp;
            }
            else{
                tmp = list2->next;
                list2->next = NULL;
                newTail->next = list2;
                newTail = list2;
                list2 = tmp;
            }
        }
        if(list1)
            newTail->next = list1;
        if(list2)
            newTail->next = list2;
        return newHead->next;
    }
	
  	//递归代码实现归并排序，大问题逐步划分，直到小问题变成2个链表调用sort()合并 或 只有1个链表时返回
    ListNode *merge(vector<ListNode *> lists,int start,int end){
        if(start==end)
            return lists[start];
        if(end-start == 1)
            return sort(lists[start],lists[end]);
        int mid = start+(end-start)/2;
        ListNode* left = merge(lists,start,mid);
        ListNode* right = merge(lists,mid+1,end);
        return sort(left,right);    
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int start = 0;
        int end = lists.size()-1;
        if(end<start)  //lists长度为0，返回NULL
            return NULL;
        return merge(lists,start,end);
    }
};