[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节点的作用是为了简化算法的实现，它的下一个节点将指向合并后的链表的头结点。

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

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

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

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

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

7. 返回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;
        }
    }
}

作者其他作品：

【Java】Spring循环依赖：原因与解决方法

OpenAI Sora来了，视频生成领域的GPT-4时代来了

[Java·算法·简单] LeetCode 14. 最长公共前缀 详细解读

【Java】深入理解Java中的static关键字

[Java·算法·简单] LeetCode 28. 找出字a符串中第一个匹配项的下标 详细解读

了解 Java 中的 AtomicInteger 类

算法题 — 整数转二进制，查找其中1的数量

https://leetcode.cn/problems/merge-two-sorted-lists/description/

Java企业应用软件系统架构演变史