【LeetCode每日一题】——LCR 078.合并 K 个升序链表

一【题目类别】

• 优先队列

二【题目难度】

• 困难

三【题目编号】

• LCR 078.合并 K 个升序链表

四【题目描述】

• 给定一个链表数组，每个链表都已经按升序排列。
• 请将所有链表合并到一个升序链表中，返回合并后的链表。

五【题目注意】

• 本题与主站 23 题相同： https://leetcode-cn.com/problems/merge-k-sorted-lists/

六【题目示例】

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

八【解题思路】

• 使用优先队列（小顶堆）解决该问题
• 小顶堆维护各个链表没有被合并的的节点的最前面的节点
• 这样我们每次都会取出所有链表中值最小的节点
• 然后依次将所有节点存入小顶堆中再将其合并为一个链表
• 最后返回结果即可

九【时间频度】

• 时间复杂度：$O(kn\times logk)$，$k$为优先队列中的元素个数，$n$为传入的链表个数
• 空间复杂度：$O(k)$，$k$为优先队列中的元素个数

十【代码实现】

1. Java语言版

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {// 定义一个类 Status，用来存储链表节点值和对应的节点指针class Status implements Comparable<Status> {int val;ListNode node;// 构造函数，初始化节点值和指针Status(int val, ListNode node) {this.val = val;this.node = node;}// 实现 Comparable 接口，按照节点值从小到大排序public int compareTo(Status status) {return this.val - status.val;}}// 合并多个有序链表public ListNode mergeKLists(ListNode[] lists) {// 定义一个优先队列（小顶堆），会根据 Status 类中的节点值进行排序PriorityQueue<Status> pQueue = new PriorityQueue<Status>();// 遍历所有链表，把每个链表的第一个节点放入优先队列for (ListNode node : lists) {if (node != null) {pQueue.offer(new Status(node.val, node));}}// 创建一个虚拟头节点和尾节点，方便构建结果链表ListNode head = new ListNode(0);ListNode tail = head;// 循环处理优先队列中的节点，直到队列为空while (!pQueue.isEmpty()) {Status min_node = pQueue.poll();tail.next = min_node.node;tail = tail.next;if (min_node.node.next != null) {pQueue.offer(new Status(min_node.node.next.val, min_node.node.next));}}// 返回合并后的链表（哑节点的下一个节点）return head.next;}
}

2. Python语言版

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = nextimport heapqclass Solution:# 定义一个类 Status，用来存储链表节点值和对应的节点指针class Status:# 构造函数，初始化节点值和指针def __init__(self, val, node):self.val = valself.node = node# 实现接口，按照节点值从小到大排序def __lt__(self, other):return self.val < other.val# 合并多个有序链表def mergeKLists(self, lists: List[ListNode]) -> ListNode:# 定义一个优先队列（小顶堆），会根据 Status 类中的节点值进行排序pQueue = []# 遍历所有链表，把每个链表的第一个节点放入优先队列for node in lists:if node is not None:heapq.heappush(pQueue, self.Status(node.val, node))# 创建一个虚拟头节点和尾节点，方便构建结果链表head = ListNode(0)tail = head# 循环处理优先队列中的节点，直到队列为空while pQueue:min_node = heapq.heappop(pQueue)tail.next = min_node.nodetail = tail.nextif min_node.node.next is not None:heapq.heappush(pQueue, self.Status(min_node.node.next.val, min_node.node.next))# 返回合并后的链表（哑节点的下一个节点）return head.next

3. 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 Status {public:int val;ListNode* node;Status(int v, ListNode* n) : val(v), node(n) {}bool operator<(const Status& other) const {return val > other.val;}
};class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {std::priority_queue<Status> pQueue;for (ListNode* node : lists) {if (node != nullptr) {pQueue.push(Status(node->val, node));}}ListNode* head = new ListNode(0);ListNode* tail = head;while (!pQueue.empty()) {Status min_node = pQueue.top();pQueue.pop();tail->next = min_node.node;tail = tail->next;if (min_node.node->next != nullptr) {pQueue.push(Status(min_node.node->next->val, min_node.node->next));}}ListNode* result = head->next;delete head;return result;}
};

十一【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C++语言版