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

//分治思想运用在K个链表中方法  两个链表合并+分治
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
  public:

    ListNode* Merge2(ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == NULL)
            return pHead2;
        if (pHead2 == NULL)
            return pHead1;
        ListNode* newList = new ListNode(0);
        ListNode* nHead;
        nHead = newList;
        while (pHead1 != NULL && pHead2 != NULL) {
            if (pHead1->val < pHead2->val) {
                newList->next = pHead1;
                pHead1 = pHead1->next;
                cout << "路过1";
            } else {
                newList->next = pHead2;
                pHead2 = pHead2->next;
                cout << "路过2";
            }
            newList = newList->next;
        }
        while (pHead1) {
            newList->next = pHead1;
            newList = newList->next;
            pHead1 = pHead1->next;
            cout << "路过3";
        }
        while (pHead2) {
            newList->next = pHead2;
            newList = newList->next;
            pHead2 = pHead2->next;
            cout << "路过4";
        }
        return nHead->next;
    }

    ListNode* merge1(vector<ListNode*>& lists, int left, int right) {
        if (left > right)
            return NULL;
        if (left == right)
            return lists[left];
        int mid = (left + right) / 2;
        return Merge2(merge1(lists, left, mid), merge1(lists, mid+1, right));

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