【前端面试常见算法题系列】23. 合并K个升序链表（困难）-一一网

“Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。”

一、题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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

二、思路分析

这道题是 leetcode 21. 合并两个有序链表的进阶版，难点在于：不止要合并两个链表，而是 lists.length 个，但幸运的是：元素中的链表是有序的，因此我们依然可以此为切入点。

21原题我们用双指针技巧解题：一个指针对应一条链表，比较指针元素的大小，以此排列，直到其中一条链表（或者两条链表）都走到末尾，如果还有没遍历完的链表，则直接将每遍历到的那部分赋值给合并后的链表（因为如果没遍历到则说明上面的值都比合并后的链表的最后一个元素还大），那么就完成了两个有序链表的合并。

而这道题也是有序的，我们可以从这个信息以及我们学过的数据结构进行思考分析。（要自己思考一下呀^_^）

其实 c++ 有一个数据结构 优先队列 可以帮助我们完成这道题，思路是这样的：
我们将数组元素（包括该元素下的每个值）都压入一个反序的优先队列，也就是最小堆，压完之后整个优先队列都是从大到小排好序的。然后我们只需要新建一条链表，依次将队列里每个元素穿起来即可。

三、AC 代码

链表定义：

/**
 * 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) {
        priority_queue<int, vector<int>, greater<int>> q;
        for (ListNode* head : lists) {
            while (head) {
                q.push(head -> val);
                head = head -> next;
            }
        }
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while (!q.empty()) {
            int node = q.top();
            q.pop();
            cur -> next = new ListNode(node);
            cur = cur -> next;
        }
        return dummy -> next;
    }
};
复制代码