题目
23. 合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] 按 升序 排列
- lists[i].length 的总和不超过 10^4
我的代码（C++）
/**
* 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) {
if (lists.empty()) {
return nullptr;
}
while (lists.size() > 1) {
int len = lists.size();
ListNode* dummyHead = new ListNode();
for (int i = 0; i < len - 1; i += 2) {
ListNode* tmp1 = lists[i];
ListNode* tmp2 = lists[i + 1];
dummyHead->next = nullptr;
ListNode* tmp = dummyHead;
while (tmp1 && tmp2) {
if (tmp1->val <= tmp2->val) {
tmp->next = tmp1;
tmp = tmp1;
tmp1 = tmp1->next;
} else {
tmp->next = tmp2;
tmp = tmp2;
tmp2 = tmp2->next;
}
}
if (tmp1) {
tmp->next = tmp1;
} else if (tmp2) {
tmp->next = tmp2;
}
lists[i] = dummyHead->next;
lists[i + 1] = nullptr;
}
for(vector<ListNode*>::iterator it = lists.begin(); it != lists.end();) {
if (!(*it)) {
lists.erase(it);
} else {
it++;
}
}
}
return lists[0];
}
};点评
因为昨天做排序链表，官方的解答中用到了自底向上的归并排序，所以这里也自然想到了这个方法，直接用于实现。
通过算是通过了，不过表现中规中矩。和官方的第一种解法差不多（第一种就不考虑了）。
官方的最后一种方法用到了优先队列，这是我没想到的。因为实际工作中不太常用到，所以不熟悉。
我一开始往stl上想过，想找一个能够快速插入、删除和排序的结构，不过思路一直在往二叉树方向飘，而STL里并没有类似实现，自己实现可能性太低，所以放弃了。
还是要对各种语言的标准库熟悉一些才更好做工程，毕竟自己一个人想算法，怎么也不如做标准库那些大神们（对我来说）。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog