## [Leetcode]23. Merge k Sorted Lists(C++)

### 题目描述

You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order.

### 例子

#### 例子 1

Input: `lists = [[1,4,5],[1,3,4],[2,6]]` Output: `[1,1,2,3,4,4,5,6]` Explanation: `The linked-lists are:` [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6

#### 例子 2

Input: `lists = []` Output: `[]`

#### 例子 3

Input: `lists = [[]]` Output: `[]`

### Constraints

• `k == lists.length`
• `0 <= k <= 10^4`
• `0 <= lists[i].length <= 500`
• `-10^4 <= lists[i][j] <= 10^4`
• `lists[i]` is sorted in ascending order.
• The sum of `lists[i].length` won’t exceed `10^4`.

### 解题思路

``````/**
* 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) {}
* };
*/
#include <queue>

class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
std::priority_queue<ListNode*, std::vector<ListNode*>, ListNodeComprare>
pq;

for (const auto& node : lists) {
if (node) {
pq.push(node);
}
}

ListNode* dummy = new ListNode();
ListNode* curr = dummy;
while (pq.size()) {
ListNode* top = pq.top();
pq.pop();
curr->next = top;
curr = curr->next;
if (top->next) {
pq.push(top->next);
}
}

return dummy->next;
}

private:
struct ListNodeComprare {
bool operator()(const ListNode* lhs, const ListNode* rhs) {
return lhs->val > rhs->val;
}
};
};
``````
• 时间复杂度: O(nlogk)
• 空间复杂度: O(k)

GitHub 代码同步地址： 23.MergeKSortedLists.cpp

Built with Hugo
Theme Stack designed by Jimmy