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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <vector>
class Solution {
public:

    ListNode * Merge2(ListNode * pHead1,ListNode * pHead2){
        if(pHead1 ==nullptr)
            return pHead2;
        if(pHead2 == nullptr)
            return pHead1;
        ListNode * head = new ListNode(0);
        ListNode * tail = head;

        while(pHead1 && pHead2){
            if(pHead1->val < pHead2->val){
                tail->next = pHead1;
                pHead1 = pHead1->next;
            }
            else{
                tail->next = pHead2;
                pHead2 = pHead2->next;
            }
            tail = tail->next;
        }
        if(pHead1){
            tail->next = pHead1;
        }
        else{
            tail->next = pHead2;
        }
        return head->next;
    }


    ListNode * divideMerge(vector<ListNode *> &lists,int left,int right){
        if(left > right)
            return nullptr;
        else if (left == right)
            return lists[left];
        int mid = (left + right) >> 1;
        return Merge2(divideMerge(lists, left, mid),divideMerge(lists, mid+1, right));
    }

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        return divideMerge(lists,0,lists.size()-1);
    }
};