分治
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;
}
};