当前位置：首页 > news >正文

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

news 2025/7/9 20:20:44

文章目录

一【题目类别】
二【题目难度】
三【题目编号】
四【题目描述】
五【题目注意】
六【题目示例】
七【题目提示】
八【解题思路】
九【时间频度】
十【代码实现】
十一【提交结果】

一【题目类别】

优先队列

二【题目难度】

困难

三【题目编号】

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 l o g k)$ ， $k$ 为优先队列中的元素个数， $n$ 为传入的链表个数
空间复杂度： $O (k)$ ， $k$ 为优先队列中的元素个数

十【代码实现】

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;}
}

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

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;}
};