首页 > 其他分享 >LeetCode23:合并K个升序链表

LeetCode23:合并K个升序链表

时间:2024-11-01 18:19:38浏览次数:3  
标签:ListNode val lists 链表 升序 节点 LeetCode23

原题地址:. - 力扣(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. 构建新链表:使用排序后的值构建一个新的升序链表。

源码实现

/**
 * 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;
        // 如果输入链表数组为空,直接返回null
        if (lists == null || lists.length == 0) {
            return result;
        }

        // 使用一个列表来存储所有链表中的节点值
        List<Integer> array = new ArrayList<>();
        // 遍历所有链表,将节点值添加到列表中
        for (int i = 0; i < lists.length; i++) {
            node(lists[i], array);
        }
        // 如果列表为空,返回null
        if (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)

标签:ListNode,val,lists,链表,升序,节点,LeetCode23
From: https://blog.csdn.net/qq_36070104/article/details/143438179

相关文章

  • 链表和数组的区别
    链表和数组是两种常用的数据结构,本文旨在详细比较链表和数组的区别包括:1.存储方式不同;2.内存利用不同;3.访问元素的效率不同;4.插入和删除操作的效率不同;5.内存分配的灵活性不同;6.应用场景不同。通过这些比较,读者将更深入地理解两者的特点,以及它们在不同应用场景下的最佳使用方法。......
  • 单链表题+数组题(快慢指针和左右指针)
    @目录说明:本文章用于“单链表题+数组题”“链表”知识一、案例说明(使用快慢指针)问题1.1判断链表是否有环问题1.2:已知链表有环,请返回这个环的起点位置问题1.3:寻找无环单链表的中点,要求:如果偶数个数以左面一个节点为中点问题1.4:寻找无环单链表的中点,要求:如果偶数个数以右面一个节......
  • 02链表算法/代码随想录
    前几天忙比赛,算法停了三天,继续开刷,不能停!!二、链表2.1删除链表中的元素两种方案无哨头:要删除节点的前一个结点指向删除节点的指向节点。头节点需要单独定义有哨头:头节点不需要单独定义实战力扣203/***Definitionforsingly-linkedlist.*publicclassLis......
  • 链表(数据结构)
    一.单链表1.1概念与结构再上一篇中我们讲到顺序表,但是顺序表也是有很多的问题,像申请的空间过多过少或者增容该才能不浪费空间,今天我们就来认识一个新的知识,叫做链表,链表也是线性表的一种,链表是一种物理存储结构上非连续、非顺序的存储结构,数据结构的逻辑顺序是通过链表中的......
  • Leetcode21:合并两个有效链表
    原题地址:.-力扣(LeetCode)题目描述将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1,1,2,3,4,4]示例2:输入:l1=[],l2=[]输出:[]示例3:输入:l1=[],l2=......
  • 相交链表
    两个链表的第一个公共结点(相交链表)题目链接:牛客||LeetCode160描述输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)例如,输入{1,2,3},{4,5},{6,7}时,两个无......
  • 代码随想录之链表刷题总结
    目录1.链表理论基础2.移除链表元素3.设计链表4.翻转链表5.两两交换链表中的节点6.删除链表中的第N个节点7.链表相交8.环形链表1.链表理论基础链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后......
  • 《链表篇》---两两交换链表中的节点(中等)
    题目传送门1.定义一个虚拟节点链接链表2.定义一个当前节点指向虚拟节点3.在当前节点的下一个节点和下下一个节点都不为null的情况下。定义node1和node2。保存当前节点后面两个节点的地址。cur.next=node2;node1.next=node2.next;node2.next=node1;cur=node1;4.......
  • 《链表篇》---删除链表的倒数第N个节点(中等)
    题目传送门 方法一:计算链表长度(迭代)1.计算链表长度,并且定义哑节点链接链表。2.从哑节点开始前进length-n次。即为被删除节点的前置节点。3.进行删除操作。4.返回哑节点的后置节点classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){......
  • 单链表题带刷(二)
    目录一、链表的回文结构1.1题目1.2解题思路二、相交链表2.1题目一、链表的回文结构1.1题目https://www.nowcoder.com/share/jump/6870342311730273670970https://www.nowcoder.com/share/jump/68703423117302736709701.2解题思路思路一:创建新链表,将原链表反......