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

分治

class Solution {
public:
    ListNode *merge(vector<ListNode *> &lists, int l, int r) {
        if (l == r) return lists[l];
        ListNode *l1, *l2, *ret = nullptr, **rret;
        rret = &ret;
        int mid = (l + r) >> 1;
        l1 = merge(lists, l, mid);
        l2 = merge(lists, mid + 1, r);
        while (l1 != nullptr && l2 != nullptr) {
            ListNode **tmp = l1->val < l2->val ? &l1 : &l2;                
            *rret = *tmp;
            rret = &((*rret) -> next);
            *tmp = (*tmp) -> next;
        }
        *rret = l1 != nullptr ? l1 : l2;
        return ret;
        
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.size()) return merge(lists, 0, lists.size() - 1);
        return nullptr;
    }
};