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

Leetcode每日一题:23. 合并 K 个升序链表(2023.8.12 C++)

目录

23. 合并 K 个升序链表

题目描述:

实现代码与解析:

优先级队列:

原理思路:


23. 合并 K 个升序链表

题目描述:

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

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

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

实现代码与解析:

优先级队列:

/*** 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:struct Node{int val;ListNode* ptr;bool operator < (const Node &node) const{return val > node.val; //小顶堆}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<Node> q; // 优先级队列for (int i = 0; i < lists.size(); i++){if (lists[i]) q.push({lists[i]->val, lists[i]}); // 入队}ListNode* head = new ListNode(); // 头节点ListNode* cur = head;while(q.size()){auto t = q.top(); q.pop(); // 出队cur->next = t.ptr;cur = cur->next;auto nt = t.ptr->next; if (nt) q.push({nt->val, nt}); // 已经出队的节点将其下一个节点入队}return head->next;}
};

原理思路:

        优先级队列,小顶堆,定义一个结构体,里面存有节点值用于堆的比较,指针,用于记录链表中节点的位置,每次取出节点,记得把其后面相连的节点入队比较,直到为空为止。很简单,不再详细解释了。

http://www.lryc.cn/news/121064.html

相关文章:

  • 越南的区块链和NFT市场调研
  • MySQL常用语句
  • Mongodb:业务应用(1)
  • 【vue】vue中按钮权限控制:
  • 【博客695】k8s subPathExpr作用
  • 微信小程序中键盘弹起输入框自动跳到键盘上方处理
  • excel将主信息和明细信息整理为多对多(每隔几行空白如何填充)
  • 卷积神经网络实现彩色图像分类 - P2
  • 【博客694】k8s kubelet 状态更新机制
  • 【博客692】grafana如何解决step动态变化时可能出现range duration小于step
  • eNSP:ibgp的破水平切割练习
  • maven是什么?安装+配置
  • 基于长短期神经网络LSTM的多分类代码
  • 利用爬虫爬取图片并保存
  • 设计模式之Bridge模式的C++实现
  • springboot异步任务
  • Flutter父宽度自适应子控件的宽度
  • 什么是 API 安全?学习如何防止攻击和保护数据
  • 简述 TCP 和 UDP 的区别以及优缺点和使用场景?
  • react进阶
  • 使用windows搭建WebDAV服务,并内网穿透公网访问【无公网IP】
  • 科技感响应式管理系统后台登录页ui设计html模板
  • Lombok的使用及注解含义
  • 实时通信应用的开发:Vue.js、Spring Boot 和 WebSocket 整合实践
  • 【C++】C++异常
  • 学生成绩管理系统V2.0
  • 【C++】开源:tinyxml2解析库配置使用
  • 如何使用webpack打包一个库library,使用webpack打包sdk.
  • 项目一:基于stm32的阿里云智慧消防监控系统
  • 【果树农药喷洒机器人】Part6:基于深度相机与分割掩膜的果树冠层体积探测方法