44 lines
894 B
C++
44 lines
894 B
C++
#include "s0023_merge_k_sorted_lists.hpp"
|
|
|
|
ListNode *S0023::mergeTwoLists(ListNode *a, ListNode *b) {
|
|
if (a == nullptr) {
|
|
return b;
|
|
} else if (b == nullptr) {
|
|
return a;
|
|
}
|
|
ListNode dummy;
|
|
ListNode *tail = &dummy;
|
|
while (a != nullptr && b != nullptr) {
|
|
if (a->val > b->val) {
|
|
tail->next = b;
|
|
b = b->next;
|
|
} else {
|
|
tail->next = a;
|
|
a = a->next;
|
|
}
|
|
tail = tail->next;
|
|
}
|
|
if (a == nullptr) {
|
|
tail->next = b;
|
|
} else {
|
|
tail->next = a;
|
|
}
|
|
return dummy.next;
|
|
}
|
|
|
|
// 分治合并
|
|
ListNode *S0023::merge(vector<ListNode *> &lists, int l, int r) {
|
|
if (l == r) {
|
|
return lists[l];
|
|
}
|
|
if (l > r) {
|
|
return nullptr;
|
|
}
|
|
int mid = (l + r) >> 1;
|
|
return mergeTwoLists(merge(lists, 1, mid), merge(lists, mid + 1, r));
|
|
}
|
|
|
|
ListNode *S0023::mergeKLists(vector<ListNode *> &lists) {
|
|
return merge(lists, 0, lists.size() - 1);
|
|
}
|