五常网站建设,发免费广告电话号码,泉州建设工程招投标信息网,阿里企业邮箱后缀文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目注意】六【题目示例】七【题目提示】八【解题思路】九【时间频度】十【代码实现】十一【提交结果】 一【题目类别】
优先队列
二【题目难度】
困难
三【题目编号】
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.length0 k 10^40 lists[i].length 500-10^4 lists[i][j] 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4
八【解题思路】
使用优先队列小顶堆解决该问题小顶堆维护各个链表没有被合并的的节点的最前面的节点这样我们每次都会取出所有链表中值最小的节点然后依次将所有节点存入小顶堆中再将其合并为一个链表最后返回结果即可
九【时间频度】
时间复杂度 O ( k n × l o g k ) O(kn × logk) O(kn×logk) k k k为优先队列中的元素个数 n n n为传入的链表个数空间复杂度 O ( k ) O(k) O(k) k 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 ComparableStatus {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 类中的节点值进行排序PriorityQueueStatus pQueue new PriorityQueueStatus();// 遍历所有链表把每个链表的第一个节点放入优先队列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, val0, nextNone):
# 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.nextC语言版
/*** 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(vectorListNode* lists) {std::priority_queueStatus 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;}
};十一【提交结果】 Java语言版 Python语言版 C语言版
