Написано: 17.03.2023
23. Объединить k сортированных списков (Merge k Sorted Lists)
Задание.
Вам предоставляется массив из k списков связанных списков, каждый связанный список отсортирован по возрастанию.
Объедините все связанные списки в один отсортированный связанный список и верните его.
Пример 1.
Входные данные: lists = [ [1,4,5], [1,3,4], [2,6] ]
Результат: [1,1,2,3,4,4,5,6]
Пояснение: Связанные списки [ 1->4->5, 1->3->4, 2->6 ] объединяются в один сортированный список: 1->1->2->3->4->4->5->6
Пример 2.
Входные данные: lists = []
Результат: []
Пример 3.
Входные данные: lists = [[]]
Результат: []
Решение.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
private:
ListNode* mergeKListsHelper(vector<ListNode*>& lists, int start, int end) {
if (start == end) {
return lists[start];
}
if (start + 1 == end) {
return merge(lists[start], lists[end]);
}
int mid = start + (end - start) / 2;
ListNode* left = mergeKListsHelper(lists, start, mid);
ListNode* right = mergeKListsHelper(lists, mid + 1, end);
return merge(left, right);
}
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode dummy;
ListNode* curr = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
curr->next = l1;
l1 = l1->next;
} else {
curr->next = l2;
l2 = l2->next;
}
curr = curr->next;
}
curr->next = l1 ? l1 : l2;
return dummy.next;
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) {
return nullptr;
}
return mergeKListsHelper(lists, 0, lists.size() - 1);
}
};