日拱一卒，LeetCode23，攻克难题从这道题开始吧
日拱一卒，LeetCode23，攻克难题从这道题开始吧
作者 | 梁唐
大家好，我是梁唐。
我们今天来看LeetCode的23题，合并K个升序链表。
这道题的难度是Hard，是的，这是一道难题。先别急着害怕，难题其实并没有那么吓人。只要心怀不畏困难的勇气，加上每天坚持的训练，不用多久就可以将难题斩于马下。
废话不多说，我们来看这道题的题意：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
题意很简单，就是让我们把K个有序的链表合并。
再来看下样例和数据范围：
最多有1e4也就是1w个链表，每个链表最多500个元素，乘一下，最多也就500w个数字。
很容易可以想到，我们可以把这些元素全部取出，存放在一个容器里，最后再对容器进行排序。最后重新组装成链表，那么这样的代码能不能通过呢？当然可以：
/**
* 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) {
vector<int> nums;
// 取出链表中所有元素，由于不知道链表长度，所以要用while循环
while (1) {
// 判断是否还有链表有元素
bool flag = false;
for (auto &list: lists) {
if (list != nullptr) {
flag = true;
nums.push_back(list->val);
list = list->next;
}
}
if (!flag) break;
}
sort(nums.begin(), nums.end());
ListNode *ret = new ListNode(0);
ListNode *pnt = ret;
for (auto x: nums) {
pnt->next = new ListNode(x);
pnt = pnt->next;
}
return ret->next;
}
};
我们并没有用什么高深的算法，也没有做复杂的推导求证，只要稍微熟悉一下链表的用法，再注意一些细节，保证代码的质量不要有bug。通过本题是非常轻松的。
如果你没有看题解，而是自己想出了方法通过的，那么相信你一定很有成就感。
虽然我们通过了题目，但其实我们的方法还不够完美。相信大家也都注意到了，有一个关键的信息被我们忽略了——链表本身都是有序的。
我们的方法固然能够解决问题，但没有利用上这个条件，最后额外进行了排序。虽然我们不确定是否还有复杂度更优的解法，但最后进行排序看起来实在是有些不太优雅。
那么问题来了，有没有办法不排序呢？当然有，除了排序之外我们还有其他的数据结构也可以维护元素的有序性。比如优先队列，优先队列可以保证队列中的元素保持有序，队首的元素最小或最大。最简单的方法就是使用优先队列代替vector，这样我们只需要把元素存进优先队列，再拿出来，就可以保证是有序的，而不再需要额外排序了，虽然复杂度上没有什么变化，但看起来优雅了许多。
/**
* 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) {
ListNode *ret = new ListNode();
ListNode *pnt = ret;
int n = lists.size();
// 传入greater<int>保证越小的元素优先级越高
priority_queue<int, vector<int>, greater<int>> que;
while (true) {
bool flag = true;
for (int i = 0; i < n; i++) {
if (lists[i] != nullptr) {
que.push(lists[i]->val);
lists[i] = lists[i]->next;
flag = false;
}
}
if (flag) break;
}
while (!que.empty()) {
pnt->next = new ListNode(que.top());
que.pop();
pnt = pnt->next;
}
return ret->next;
}
};
虽然我们使用了优先队列，但根本的思路还是一样的，把所有元素取出来，再想办法让它们有序，最后返回。
有没有办法直接按照元素的排序来获取元素呢？这样拿到的就是有序的，就不用再额外调整顺序了。
当然也有办法，办法也不复杂，还是使用优先队列。之前我们是一股脑把所有元素统统塞进了优先队列当中，再一个一个取出来保证的有序性。这一次我们其实可以把元素和链表进行绑定，每次从头部元素最小的链表当中取出头部的元素来。
这样一样可以保证我们取出的元素都是有序的，当从链表取出了元素之后，我们把指针移动一格。如果链表还不为空，那么我们再把它和顶部的元素捆绑，一起塞入队列里。
思路稍微有所变化，但其实也不难，理解了优先队列很容易想到。
只不过实现的时候稍稍有一点点困难，因为我们要把具体的数值和链表捆绑一起放入队列，所以需要额外实现一个结构体。并且由于优先队列需要对结构体进行排序，所以我们还需要重载结构体的比较运算符。因此会稍稍麻烦一些。
/**
* 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:
struct P {
int v;
ListNode* ptr;
P(){}
P(int val, ListNode* p): v(val), ptr(p) {}
// 重载运算符
bool operator>(const P& b) const {
return v > b.v;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<P, vector<P>, greater<P>> que;
for (auto &list: lists) {
if (list != nullptr) que.push(P(list->val, list));
}
ListNode* ret = new ListNode(0);
ListNode* pnt = ret;
while (!que.empty()) {
auto f = que.top();
que.pop();
pnt->next = new ListNode(f.v);
pnt = pnt->next;
auto p = f.ptr->next;
if (p != nullptr) que.push(P(p->val, p));
}
return ret->next;
}
};
如果你对归并排序比较熟悉，也很容易想到，我们可以仿照归并排序的思路，通过分治的方法将这些有序的链表归并在一起。
/**
* 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* mergeTwoLists(ListNode* la, ListNode* lb) {
if (la == nullptr) return lb;
if (lb == nullptr) return la;
ListNode* ret = new ListNode(0);
ListNode* ptr = ret;
while (la != nullptr || lb != nullptr) {
if (la == nullptr) {
ptr->next = new ListNode(lb->val);
lb = lb->next;
ptr = ptr->next;
continue;
}
if (lb == nullptr) {
ptr->next = new ListNode(la->val);
la = la->next;
ptr = ptr->next;
continue;
}
if (la->val < lb->val) {
ptr->next = new ListNode(la->val);
la = la->next;
}else {
ptr->next = new ListNode(lb->val);
lb = lb->next;
}
ptr = ptr->next;
}
return ret->next;
}
ListNode* merge(vector<ListNode*>& lists, int l, int r) {
if (l+1 == r) return lists[l];
if (l >= r) return nullptr;
return mergeTwoLists(merge(lists, l, (l + r) >> 1), merge(lists, (l + r) >> 1, r));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size());
}
};
如果你发现归并的思路比较难实现，也可以把这些链表依次两两归并……
由于数据范围限制不是非常严，所以这道题的思路是多种多样的，上述的这些方法都可以通过。
这些方法彼此之间没有什么优劣，复杂度也不会相差太多。使用什么方法并不重要，重要的是，你会发现LeetCode中的难题也就这么回事。只要冷静思考，仔细分析，并不是完全一筹莫展的。
如果你曾畏惧于LeetCode中的难题，希望这道题能够帮助你转变观念。
腾讯云开发者
