题解 | #合并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* pHead1, ListNode* pHead2) {//对于两个链表的合并
        ListNode* p1 = pHead1,*p2 = pHead2;
        if(p1 == nullptr) return p2;
        if(p2 == nullptr) return p1;
        ListNode* now = new ListNode(-1);
        ListNode* dumb = now;
        while(p1 && p2){
            if(p1->val<p2->val){
                now->next = p1;
                now = now->next;
                p1 = p1->next;
            }
            else{
                now->next = p2;
                now = now->next;
                p2 = p2->next;
            }
        }
        if(p1) now->next = p1;
        if(p2) now->next = p2;
        return dumb->next;
    }
    ListNode* mergelist(vector<ListNode*>& lists,int l,int r){//分治算法
        if(l==r){//终止条件：l==r,l>r两个
            return lists[l];
        }
        if(l>r) return nullptr;
        int mid = l+((r-l)>>1);
        return Merge(mergelist(lists, l, mid),mergelist(lists, mid+1, r));之后不断分开就好了
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        return mergelist(lists, 0, lists.size()-1);//分治算法，注意输入条件
    }
};