自己的做法
算法思想
使用队列，将每个链表头指针依次入队。每两个有序链表进行一次合并，然后将他们合并后的链表头指针放入队尾。
循环进行，直到队列中只剩一个元素，就是最终全部合并后的链表头指针。
特殊情况：当链表数组为空，则返回空；链表数组长度为1，则返回该元素。
算法实现
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) {
return nullptr;
} else if(lists.size() == 1) {
return lists[0];
}
queue<ListNode *> q;
for(int i = 0; i < lists.size(); i++) {
q.push(lists[i]);
}
while (q.size() != 1) {
ListNode * list1 = q.front();
q.pop();
ListNode * list2 = q.front();
q.pop();
ListNode * merged = merge(list1, list2);
q.push(merged);
}
return q.front();
}
ListNode * merge(ListNode * l1, ListNode * l2) {
if(l1 == nullptr) return l2;
if(l2 == nullptr) return l1;
ListNode * dummy = new ListNode();
ListNode * node = dummy, * node1 = l1, * node2 = l2;
while (node1 != nullptr && node2 != nullptr) {
if(node1->val < node2->val) {
node->next = node1;
node1 = node1->next;
} else {
node->next = node2;
node2 = node2->next;
}
node = node->next;
}
if (node1 != nullptr) {
node->next = node1;
}
if(node2 != nullptr) {
node->next = node2;
}
return dummy->next;
}
};
|
性能分析
设有k个链表，每个链表最长长度为n。
时间复杂度：第一轮合并2k组链表，每一组时间代价是O(2n)；第二轮合并4k，时间代价为O(4n)
总时间复杂度为O(kn×logk)。
空间复杂度：O(k)。
另一种做法
算法思想
每次都从所有链表的当前节点中找出一个最小节点，然后链接该节点。然后该链表遍历指针指向下一个节点。一直到所有链表遍历指针都为空，即所有结点都被连接到有序链表上。循环结束。
类似于合并两个有序链表的做法。
算法实现
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
34
35
36
37
38
| class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) {
return nullptr;
} else if(lists.size() == 1) {
return lists[0];
}
ListNode * dummy = new ListNode(0);
ListNode * pre = dummy;
int size = lists.size();
while (pre != nullptr) {
int minNumber = INT_MAX;
int index = -1;
for(int i = 0; i < size; i++) {
if(lists[i] != nullptr && lists[i]->val < minNumber) {
minNumber = lists[i]->val;
index = i;
}
}
if(index != -1) {
pre->next = lists[index];
pre = pre->next;
lists[index] = lists[index]->next;
} else {
pre->next = nullptr;
pre = nullptr;
}
}
return dummy->next;
}
};
|
性能分析
时间复杂度：O(mn)，m为总的节点个数，n为链表个数。
空间复杂度：O(1)。
参考做法
算法思想
使用优先队列。
优先队列：普通队列是元素在队列尾添加，在队列头删除。在优先队列中，元素被赋予优先级。当从队列弹出时，会首先弹出具有最高优先级的元素。即优先队列具有最高级先出的行为特征。
初始将每个链表头节点依次(判空后)加入优先队列，优先级就是每个节点的值。最高优先级是最小值。
然后从队列中删除最高优先级节点，并添加到已排序链表末尾。判断该节点是否有下一个节点，如果有那么将下一个节点添加到优先队列。
当队列为空，证明所有结点排序完成。
算法实现
C++中，优先队列默认会从大到小排列元素。所以如果要改变默认优先级的话。需要重载operator运算符 <。
因为C++优先队列在比较优先级时，会使用该符号比较两个元素大小。
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
34
| class Solution {
struct Status {
int val;
ListNode *ptr;
bool operator < (const Status &rhs) const {
return val > rhs.val;
}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<Status> q;
for(int i = 0; i < lists.size(); i++) {
if (lists[i]) {
q.push({lists[i]->val, lists[i]});
}
}
ListNode * head = new ListNode();
ListNode * pre = head;
while (!q.empty()) {
ListNode * node = q.top().ptr;
q.pop();
pre->next = node;
pre = pre->next;
if(node->next) {
q.push({node->next->val, node->next});
}
}
return head->next;
}
};
|
性能分析
设有k个链表，每个链表最长长度为n。
时间复杂度：优先队列中元素不超过k个，插入和删除的时间代价为O(logk)。最多有kn个点，每个节点都被插入删除依次，所有时间复杂度为O(kn×logk)。
空间复杂度：O(k)。