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

W:

• 利用归并排序，把每个链表分开，用l1,l2接受，再两两合并
  N：
• 遇到数组，判断是否为空；
• 遇到链表，判断是否为空指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoList(ListNode* l1, ListNode* l2){
        if(l1== nullptr){
            return l2;
        }
        if(l2== nullptr){
            return l1;
        }
        if(l1->val<=l2->val){
            l1->next= mergeTwoList(l1->next,l2);
            return l1;
        }
        else{
            l2->next= mergeTwoList(l1,l2->next);
            return l2;
        }
    }
    ListNode* mergeSort(vector<ListNode *> &lists,int l,int r){
        if(l>=r){
            return lists[l];
        }
        int mid= l +(r-l)/2;
        ListNode* l1=mergeSort(lists,l,mid);
        ListNode* l2=mergeSort(lists,mid+1,r);
        return mergeTwoList(l1,l2);//分完就合并
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int len = lists.size();
        if( len ==0 || lists[0]== nullptr ){
            //一遇到链表首先想到去判断是否空，这里需要先判断大小
            return nullptr;
        }
        return mergeSort(lists,0,len-1);
    }
};