LeetCode 0023 - Merge k Sorted Lists
# Hints
- 链表 + 优先队列
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
Merge sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
# 题意
给定 个有序链表,要求将其中所有节点合并为一个新的有序链表。
# 题解
我没明白为什么这道题被设为Hard,我觉得顶多是Medium……
暴力的做法很显然,类似LeetCode 0021,我们维护 个指针,每次取其中的最小者递进,时间复杂度为 ,其中 为节点总数。
上述 “-指针扫描” 的方法低效的原因在于,对于每个节点我们都需要比较 次,而在LeetCode 0021中我们只需要比较 次。
我们考虑维护一个优先队列,将所有指针放入其中,以其所指节点的键值大小排序,每次取出堆顶指针递进,这样我们就将 的比较优化至 ,那么总的时间复杂度为 。
细节问题:
- 注意特判空链表。
# AC代码
/**
* 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 {
public:
ListNode * mergeKLists(vector<ListNode *> & lists) {
// 初始化
typedef ListNode * pNode;
auto cmp = [](const pNode & p, const pNode & q) {
return (p->val > q->val);
};
priority_queue<pNode, vector<pNode>, decltype(cmp)> pq(cmp);
for (auto l : lists) {
if (l != nullptr) {
pq.push(l);
}
}
pNode head = nullptr;
// 主循环
pNode p = nullptr;
while (!pq.empty()) {
// 出队
pNode l = pq.top();
pq.pop();
// 插入
if (head == nullptr) {
head = l;
} else {
p->next = l;
}
p = l;
// 入队
l = l->next;
if (l != nullptr) {
pq.push(l);
}
}
// 返回
return head;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01