Leetcode 23.合并K个排序链表

题目描述

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

1
2
3
4
5
6
7
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

题目分析

Leetcode 21.合并两个有序链表, 将所有节点放入优先队列后建新表.

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct comp{ // 自定义排序函数
bool operator()(ListNode* &a, ListNode* &b) {
return a->val > b->val;
}
};

class Solution {
public:
priority_queue<ListNode*, vector<ListNode*>, comp> q; // 用优先队列储存节点

ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) return NULL; // 如果数组为空则返回NULL
ListNode* it;
for(int i=0; i<lists.size(); ++i) { // 遍历所有表并将每个表中所有节点存入优先队列
it = lists[i];
while(it != NULL) {
q.push(it);
it = it->next;
}
}
if(q.size() == 0) return NULL; // 如果数组中只有空节点则返回NULL
ListNode* res = q.top();
q.pop();
it = res;
while(q.size() != 0) {
it->next = q.top();
it = it->next;
q.pop();
}
it->next = NULL; // ***将最后一个节点的next设为NULL***
return res;
}
};
0%