【LeetCode Hot 100】23. 合并K个升序链表

题目描述

看到这个题目会想起之前做过的合并2个升序链表。在那个题目中，由于两个链表都已经是升序的，可以将两个链表的元素进行逐个比较并添加到答案链表中。但是在本题中，每次循环都需要在k个链表的当前元素中找出最小的，而且需要在所有k个链表都遍历完之后跳出循环，所以效率比较低。

class Solution {
public:bool checkIsEnd(vector<ListNode*>& lists) {for (int i = 0; i < lists.size(); i++) {if (lists[i] != nullptr) return false;}return true;}ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.empty()) return nullptr;ListNode* dummy = new ListNode();ListNode* p = dummy;int k = lists.size();while (true) {if (checkIsEnd(lists)) break;ListNode* minNode = nullptr;int minNodeIdx = -1;for (int i = 0; i < k; i++) {if (lists[i] == nullptr) continue;if (minNode == nullptr || minNode->val > lists[i]->val) {minNode = lists[i];minNodeIdx = i;}}p->next = minNode;p = p->next;lists[minNodeIdx] = lists[minNodeIdx]->next;}return dummy->next;}
};

这种方法中影响时间效率的主要在于：每次循环都需要首先判断指针是否已经到达链表结尾，以及每次比较k个元素的最小值都需要遍历k个元素。这里我的一个想法是优化第一个点：使用一个bitmap存储第i个链表是否已经达到结尾，这样直接进行位运算比通过循环进行判断效率高得多，但是由于需要k位长的bit串，而题目中k的设置可以非常大，超过计算机的极限，因此这个方法不太合适。

能否使用优先队列（堆）解决k个元素的最小值的问题？可以构建一个优先队列，内部维护k个当前链表结点，每次pop出最小的结点（相当于第一种方法中将最小结点加入答案链表中），再把后面一个结点加入优先队列中（相当于第一种方法中将指针向前移动一个结点），这样循环，直到优先队列中没有剩余元素为止，说明所有k个链表中的所有元素已经比较完毕了。

class Solution {
public:struct Node {ListNode* ptr;bool operator<(const Node& rhs) const {return ptr->val > rhs.ptr->val;}};priority_queue<Node> q;ListNode* mergeKLists(vector<ListNode*>& lists) {for (ListNode* node : lists) {if (node != nullptr) {q.push({node});}}ListNode *head = new ListNode(), *tail = head;while (!q.empty()) {Node node = q.top();q.pop();tail->next = node.ptr;tail = tail->next;if (node.ptr->next) {q.push({node.ptr->next});}}return head->next;}
};

其实从合并2个有序链表的想法出发，可以采用类似分治、合并的方法，比如：顺序合并，用一个链表ans来维护已经合并的链表，然后循环k次，第i次合并第i个链表，最终把所有链表合并进去；分治合并，将k个链表分组配对，并将每一对中的链表进行两两合并，如此进行多轮合并直到剩下一个链表作为答案。这两种方法也是官方题解给出的前两种解法，想法是将问题归约为合并2个有序链表的方法，并直接利用。