题解 | #先分治后合并合并k个已排序的链表#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *merge(ListNode *p1,ListNode *p2){
        if(p1 == nullptr) return p2;
        if(p2 == nullptr) return p1;
        ListNode *head = new ListNode(0);
        ListNode *cur = head;
        while (p1!=nullptr && p2!=nullptr) {
            if(p1->val <= p2->val){
                cur->next = p1;
                p1= p1->next;
            } 
            else{
                cur->next = p2;
                p2=p2->next;
            }
            cur = cur->next;
    }
        if(p1) cur->next=p1;
        else cur->next = p2;
        return head->next;
    }
    ListNode *div(vector<ListNode *> &lists,int left,int right){
        if(left > right) return nullptr;
        else if(left == right){
            return lists[left];
        }
        int mid = (left + right) / 2;
        return merge(div(lists,left,mid),div(lists,mid+1,right));
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        return div(lists,0,lists.size()-1);
    }
};