題目描述
合并 k 個(gè)排序鏈表光涂，返回合并后的排序鏈表齐唆。請(qǐng)分析和描述算法的復(fù)雜度律秃。
示例:
輸入:
[
1->4->5,
1->3->4,
2->6
]
輸出: 1->1->2->3->4->4->5->6
分析
通過(guò)優(yōu)先級(jí)隊(duì)列查找K個(gè)有序鏈表中的最小元素表頭爬橡，鏈接到有序鏈表中去，表頭把下一個(gè)元素插入到優(yōu)先級(jí)隊(duì)列
代碼
/**
* 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/
