首页 > 其他分享 >Leetcode21:合并两个有效链表

Leetcode21:合并两个有效链表

时间:2024-10-31 20:49:13浏览次数:8  
标签:ListNode 合并 next 链表 l2 l1 Leetcode21 节点

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

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

提示:

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

实现思路

  1. 输入检查:首先检查两个链表的头节点。如果一个链表为空,直接返回另一个链表的头节点。
  2. 优先队列(最小堆):使用一个优先队列来存储两个链表中的节点。通过重写比较器,确保队列中的节点按值升序排列。
  3. 遍历链表:将两个链表中的所有节点依次加入优先队列。在添加节点后,断开当前节点与后继节点的连接,以避免内存泄漏。
  4. 构建合并链表:从优先队列中依次取出节点,构建合并后的链表。使用一个临时节点指针来维护链表的尾部。
  5. 返回结果:返回合并后链表的头节点。

源码实现

/**
 * 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 mergeTwoLists(ListNode l1, ListNode l2) {
        // 检查链表是否为空
        if (l1 == null) { return l2; } // 如果l1为空,返回l2
        if (l2 == null) { return l1; } // 如果l2为空,返回l1

        // 使用优先队列来存储链表节点
        PriorityQueue<ListNode> node = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val; // 按节点值升序排列
            }
        });

        // 遍历两个链表并将节点加入优先队列
        while (l1 != null || l2 != null) {
            if (l1 != null) {
                node.add(l1); // 添加l1节点
                ListNode next = l1.next; // 记录下一个节点
                l1.next = null; // 断开当前节点与后继的连接
                l1 = next; // 移动到下一个节点
            }
            if (l2 != null) {
                node.add(l2); // 添加l2节点
                ListNode next = l2.next; // 记录下一个节点
                l2.next = null; // 断开当前节点与后继的连接
                l2 = next; // 移动到下一个节点
            }
        }

        // 从优先队列中取出节点构建合并链表
        ListNode result = node.poll(); // 取出第一个节点作为合并链表的头
        ListNode temp = result; // 使用temp指针维护合并链表的尾部
        while (node.peek() != null) {
            ListNode tag = node.poll(); // 取出下一个节点
            temp.next = tag; // 将当前节点链接到合并链表的尾部
            temp = tag; // 更新temp指针
        }
        return result; // 返回合并后的链表头
    }
}

复杂度分析

  • 时间复杂度:O((m + n) log(m + n)),其中 m 和 n 分别是两个链表的长度。我们将所有节点加入优先队列的时间复杂度为 O(m + n),而每次从优先队列中取出节点的时间复杂度为 O(log(m + n)),因此总体复杂度为 O((m + n) log(m + n))。

  • 空间复杂度:O(m + n),我们在优先队列中存储了两个链表的所有节点,因此需要 O(m + n) 的空间。

标签:ListNode,合并,next,链表,l2,l1,Leetcode21,节点
From: https://blog.csdn.net/qq_36070104/article/details/143416965

相关文章

  • Unity中的网格与材质球合并
    很多时候我们需要把具有相同shader的材质球合并,从而减少drawcall的产生。 比如九龙战里面,一个人物带有10个部位,10个部位各自来自不同的fbx文件,加上身体,就有11个材质球,占上11个drawcall。如果主城里面跑着10个角色,光人物就占了110个drawcall!所以这种时候材质球合并是必须的。(下......
  • 相交链表
    两个链表的第一个公共结点(相交链表)题目链接:牛客||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){......
  • 代码随想录算法训练营day31| 56. 合并区间 738.单调递增的数字
    学习资料:https://programmercarl.com/0056.合并区间.html#算法公开课贪心PART5over学习记录:56.合并区间(也是找重叠区间,但是是跟result[-1]比,只用比右边界;更新result[-1][1]为更大值)点击查看代码classSolution(object):defmerge(self,intervals):"""......
  • 单链表题带刷(二)
    目录一、链表的回文结构1.1题目1.2解题思路二、相交链表2.1题目一、链表的回文结构1.1题目https://www.nowcoder.com/share/jump/6870342311730273670970https://www.nowcoder.com/share/jump/68703423117302736709701.2解题思路思路一:创建新链表,将原链表反......
  • C语言判断单链表是否相交
    ////CreatedbyAdministratoron2024/10/29.//#ifndefLINK_H#defineLINK_H/***链表的结构体*/typedefstructLink{intelement;structLink*next;}link;#endif//LINK_H////判断单链表是否相交//CreatedbyAdministratoron2024/10/30......
  • C语言链表
    ////CreatedbyAdministratoron2024/10/29.//#ifndefLINK_H#defineLINK_H/***链表的结构体*/typedefstructLink{intelement;structLink*next;}link;#endif//LINK_H////链表//CreatedbyAdministratoron2024/10/28.//#pragmao......
  • C语言链表反转的四种方法
    ////CreatedbyAdministratoron2024/10/29.//#ifndefLINK_H#defineLINK_H/***链表的结构体*/typedefstructLink{intelement;structLink*next;}link;#endif//LINK_H////四种链表反转算法//CreatedbyAdministratoron2024/10/29.......