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

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