[Java·算法·中等] LeetCode21. 合并两个有序链表

简介: [Java·算法·中等] LeetCode21. 合并两个有序链表

题目

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

示例

示例1

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

输出:[1,1,2,3,4,4]

示例2

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

输出:[]

示例3

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

输出:[0]


提示

👉️ 力扣原文

/**
 * 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 list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        else if(list2==null){
            return list1;
        }
        else if(list2.val > list1.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }
        else{
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
 
 
    }
}

详细解读

这段代码实现了合并两个升序链表的算法。让我们逐步解读:

  1. 首先,创建一个名为dummy的虚拟头结点(dummy node),其值为0。这个dummy节点的作用是为了简化算法的实现,它的下一个节点将指向合并后的链表的头结点。


  1. 创建一个名为current的指针,初始化为dummy节点,用于迭代合并后的链表。


  1. 在一个while循环中,不断比较两个链表当前节点的值,选取其中较小的节点添加到合并后的链表中。循环的条件是两个链表都不为空。


  1. 如果l1的值小于l2的值,则将current的下一个节点指向l1,并将l1指针向后移动一位;否则将current的下一个节点指向l2,并将l2指针向后移动一位。


  1. 不断迭代直到其中一个链表到达末尾。


  1. 最后,如果其中一个链表还有剩余的节点,则直接将剩余链表接在合并后链表的末尾。


  1. 返回dummy节点的下一个节点,即合并后链表的头结点。

这个算法的时间复杂度是O(m + n),其中m和n分别是两个输入链表的长度,因为它只需遍历每个节点一次。

idea上代码运行

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}
 
public class MergeTwoSortedLists {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        
        if (l1 != null) {
            current.next = l1;
        }
        
        if (l2 != null) {
            current.next = l2;
        }
        
        return dummy.next;
    }
    
    public static void main(String[] args) {
        // Example usage:
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);
        
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);
        
        MergeTwoSortedLists merger = new MergeTwoSortedLists();
        ListNode merged = merger.mergeTwoLists(l1, l2);
        
        // Print the merged list
        while (merged != null) {
            System.out.print(merged.val + " ");
            merged = merged.next;
        }
    }
}
目录
打赏
0
2
2
0
52
分享
相关文章
探究‘公司禁用 U 盘’背后的哈希表算法与 Java 实现
在数字化办公时代,信息安全至关重要。许多公司采取“禁用U盘”策略,利用哈希表算法高效管理外接设备的接入权限。哈希表通过哈希函数将设备标识映射到数组索引,快速判断U盘是否授权。例如,公司预先将允许的U盘标识存入哈希表,新设备接入时迅速验证,未授权则禁止传输并报警。这有效防止恶意软件和数据泄露,保障企业信息安全。 代码示例展示了如何用Java实现简单的哈希表,模拟公司U盘管控场景。哈希表不仅用于设备管理,还在文件索引、用户权限等多方面助力信息安全防线的构建,为企业数字化进程保驾护航。
Java 实现局域网电脑屏幕监控算法揭秘
在数字化办公环境中,局域网电脑屏幕监控至关重要。本文介绍用Java实现这一功能的算法,涵盖图像采集、数据传输和监控端显示三个关键环节。通过Java的AWT/Swing库和Robot类抓取屏幕图像,使用Socket进行TCP/IP通信传输图像数据,并利用ImageIO类在监控端展示图像。整个过程确保高效、实时和准确,为提升数字化管理提供了技术基础。
85 15
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
128 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
79 16
企业局域网监控软件中 Java 优先队列算法的核心优势
企业局域网监控软件是数字化时代企业网络安全与高效运营的基石,犹如一位洞察秋毫的卫士。通过Java实现的优先队列算法,它能依据事件优先级排序,确保关键网络事件如异常流量、数据泄露等被优先处理,保障系统稳定与安全。代码示例展示了如何定义网络事件类并使用PriorityQueue处理高优先级事件,尤其在面对疑似风险时迅速启动应急措施。这一核心技术助力企业在复杂网络环境中稳健前行,护航业务腾飞。
65 32
|
4月前
|
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
157 0
剖析基于Java算法驱动的智能局域网管控之道
本文探讨了基于Java语言的局域网控制方案,结合链表数据结构与令牌桶算法,解决设备管理和流量调度难题。通过链表灵活存储网络设备信息,实现高效设备管理;令牌桶算法则精准控制流量,确保网络平稳运行。二者相辅相成,为校园、企业等局域网提供稳固高效的控制体系,保障业务连续性和数据安全。
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
68 6
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等