[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;
        }
    }
}
相关文章
|
8天前
|
设计模式 安全 Java
Java面试题:设计模式如单例模式、工厂模式、观察者模式等在多线程环境下线程安全问题,Java内存模型定义了线程如何与内存交互,包括原子性、可见性、有序性,并发框架提供了更高层次的并发任务处理能力
Java面试题:设计模式如单例模式、工厂模式、观察者模式等在多线程环境下线程安全问题,Java内存模型定义了线程如何与内存交互,包括原子性、可见性、有序性,并发框架提供了更高层次的并发任务处理能力
25 1
|
8天前
|
算法 Java
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
18 1
|
6天前
|
存储 算法 Java
分布式自增ID算法---雪花算法(SnowFlake)Java实现
分布式自增ID算法---雪花算法(SnowFlake)Java实现
|
8天前
|
存储 缓存 安全
Java面试题:介绍一下jvm中的内存模型?说明volatile关键字的作用,以及它如何保证可见性和有序性。
Java面试题:介绍一下jvm中的内存模型?说明volatile关键字的作用,以及它如何保证可见性和有序性。
12 0
|
8天前
|
算法 Java 程序员
Java面试题:解释Java的垃圾回收机制,包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
Java面试题:解释Java的垃圾回收机制,包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
11 0
|
8天前
|
算法 Java 开发者
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
11 0
|
8天前
|
存储 算法 Java
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
9 0
|
1月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
1月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
1月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
14 2