LeetCode23:合并K个升序链表

server/2024/11/28 19:34:17/

原题地址:. - 力扣(LeetCode)

题目描述

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

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

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

实现思路

题目要求合并 k 个升序链表,返回一个升序的新链表。可以使用以下思路来解决这个问题:

思路:

  1. 提取节点值:遍历所有链表,将每个节点的值提取到一个数组或列表中。
  2. 排序:对提取出的节点值进行排序。
  3. 构建新链表:使用排序后的值构建一个新的升序链表

源码实现

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 {public ListNode mergeKLists(ListNode[] lists) {// 初始化结果链表ListNode result = null;// 如果输入链表数组为空,直接返回nullif (lists == null || lists.length == 0) {return result;}// 使用一个列表来存储所有链表中的节点值List<Integer> array = new ArrayList<>();// 遍历所有链表,将节点值添加到列表中for (int i = 0; i < lists.length; i++) {node(lists[i], array);}// 如果列表为空,返回nullif (array.size() == 0) {return result;}// 将列表转换为数组并排序Integer[] ts = array.toArray(new Integer[array.size()]);Arrays.sort(ts);// 创建新链表的头节点result = new ListNode(ts[0]);ListNode dummy = result; // 使用dummy指针帮助构建链表// 遍历排序后的数组,构建链表for (int i = 1; i < ts.length; i++) {ListNode temp = new ListNode(ts[i]);dummy.next = temp; // 将新节点连接到链表dummy = temp; // 移动dummy指针}return result; // 返回合并后的链表}// 辅助函数:遍历链表并将节点值添加到列表中public void node(ListNode node, List<Integer> list) {while (node != null) {list.add(node.val); // 将节点值添加到列表node = node.next; // 移动到下一个节点}}
}

复杂度分析

  • 时间复杂度

    • 提取所有链表中的值需要 O(N),其中 N 是所有链表节点的总数。
    • 排序的时间复杂度为 O(N log N),因此整体时间复杂度为 O(N log N)
  • 空间复杂度

    • 使用 O(N) 的空间存储所有节点的值。
    • 另外还需要 O(1) 的空间来构建新的链表(指针变量),所以总体空间复杂度为 O(N)

http://www.ppmy.cn/server/137687.html

相关文章

【每日C/C++问题】

一、C/C中数组定义和初始化的方式有哪些&#xff1f; int arr[100]; // 定义了数组arr&#xff0c;并未对数组进行初始化int arr[100] {1, 2}; // 定义并初始化了数组arr前两个元素&#xff0c;其他元素为0int arr[3] {1, 2, 3}; // 定义并初始化了数组arr所有元素int arr[]…

SpringBoot集成ELK收集日志管理

ELK集成是没有代码侵入的&#xff0c;主要是吃服务器内存&#xff0c;只需要部署启动这三个服务&#xff0c;然后项目的资源日志配置指定日志输出到 logstash服务器就可以了。 1、好处就是开发人员不用依赖服务器来定位异常了&#xff0c;服务器一般需要借助VPN登录&#xff0…

我在命令行下学日语

同一个动作重复 300 遍&#xff0c;肌肉就会有记忆&#xff0c;重复 600 遍&#xff0c;脊柱就会有记忆&#xff0c;学完五十音图不熟练&#xff0c;经常遗忘或者要好几秒才想得起来一个怎么办&#xff1f;没关系&#xff0c;我做了个命令行下的小游戏 KanaQuiz 来帮助你记忆&a…

ubuntu启动慢,如何看启动耗时分布

ubuntu启动慢&#xff0c;如何看启动耗时分布 在Ubuntu系统中&#xff0c;如果您想检查启动过程中每个过程的耗时分布&#xff0c;可以使用systemd-analyze工具。这个工具可以帮助您诊断启动过程中哪些服务或步骤占用了较多时间。 查看总体启动时间&#xff1a; 要查看系统启动…

Angular中ChangeDetectorRef.detectChanges是如何实现的,对比vue种的nextTick有何不同

ChangeDetectorRef.detectChanges的介绍&#xff1a; ChangeDetectorRef.detectChanges() 是 Angular 中用于手动触发变更检测的方法。它的主要作用是立即检查组件的视图和数据绑定&#xff0c;更新界面以反映模型数据的变化。detectChanges() 是通过 Angular 的变更检测机制来…

Python基础保姆级讲解(3)

条件语句 1.if if condition: # 当条件为真时执行这里的代码,否则不执行这里 year1993 if year%40:print("year能被4整除")2.if-else if condition: # 当条件为真时执行这里的代码 else: # 如果前面的条件都为假&#xff0c;执行这里的代码 year1993 if yea…

优化低代码开发平台用户体验:功能树导航设计探讨

功能树的构建与应用在当今快速发展的软件开发环境中&#xff0c;低代码开发平台因其简化开发流程和提高开发效率而受到广泛关注。低代码开发平台中的导航功能通常以功能树的形式呈现&#xff0c;帮助用户快速找到所需的功能模块。功能树是一种层次结构&#xff0c;展示了各个功…

matplotlilb画图

matplotlib matplotlib 是 Python 中一个强大而灵活的绘图库&#xff0c;广泛用于数据可视化。它允许创建多种类型的图表&#xff0c;包括线图、散点图、柱状图、饼图、直方图等。matplotlib 的基础是 pyplot 模块&#xff0c;它为绘图提供了简单的接口。这里详细讲解一下 mat…