题目描述
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
分析
通过优先级队列查找K个有序链表中的最小元素表头，链接到有序链表中去，表头把下一个元素插入到优先级队列
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
struct cmp {
bool operator () (ListNode * a, ListNode * b) {
return a->val > b->val;
}
};
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> q;
for (int i = 0; i < lists.size(); ++i) {
if (lists[i] != NULL) {
q.push(lists[i]);
}
}
ListNode dumy(0);
auto* head = &dumy;
while (!q.empty()) {
auto& tmp = q.top();
head->next = tmp;
head = head->next;
if(tmp->next != NULL) {
q.push(tmp->next);
}
q.pop();
}
return dumy.next;
}
};
题目链接
https://leetcode-cn.com/problems/merge-k-sorted-lists/description/
