题解 | #合并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* l1, ListNode* l2){
        ListNode *dummyHead = new ListNode(-1);
        ListNode *p = dummyHead;
        while(l1 != NULL && l2 != NULL){
            if(l1 -> val <= l2 -> val) p -> next = new ListNode(l1 -> val), l1 = l1 -> next;
            else p -> next = new ListNode(l2 -> val), l2 = l2 -> next;
            p = p -> next;
        }
        while(l1 != NULL){
            p -> next = new ListNode(l1 -> val);
            l1 = l1 -> next;
            p = p -> next;
        }
        while(l2 != NULL){
            p -> next = new ListNode(l2 -> val);
            l2 = l2 -> next;
            p = p -> next;
        }
        return dummyHead -> next;
    }
    ListNode* mergeLists(vector<ListNode*> & lists, int left, int right){
        if(left < right){
            int mid = left + (right - left) / 2;
            ListNode* pLeft = mergeLists(lists, left , mid);
            ListNode* pRight = mergeLists(lists, mid + 1, right);
            return merge(pLeft, pRight);
        }
        if(left == right) return lists[left];
        return NULL;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        return mergeLists(lists, 0, lists.size() - 1);
    }
};