🌈个人主页：人不走空
💖系列专栏：算法专题
⏰诗词歌赋：斯是陋室，惟吾德馨
目录
🌈个人主页：人不走空
💖系列专栏：算法专题
⏰诗词歌赋：斯是陋室，惟吾德馨
题目
示例
示例1
示例2
示例3
提示
详细解读
idea上代码运行
作者其他作品：
题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
示例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; } }}
详细解读
这段代码实现了合并两个升序链表的算法。让我们逐步解读：
首先，创建一个名为dummy的虚拟头结点（dummy node），其值为0。这个dummy节点的作用是为了简化算法的实现，它的下一个节点将指向合并后的链表的头结点。
创建一个名为current的指针，初始化为dummy节点，用于迭代合并后的链表。
在一个while循环中，不断比较两个链表当前节点的值，选取其中较小的节点添加到合并后的链表中。循环的条件是两个链表都不为空。
如果l1的值小于l2的值，则将current的下一个节点指向l1，并将l1指针向后移动一位；否则将current的下一个节点指向l2，并将l2指针向后移动一位。
不断迭代直到其中一个链表到达末尾。
最后，如果其中一个链表还有剩余的节点，则直接将剩余链表接在合并后链表的末尾。
返回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企业应用软件系统架构演变史
