当前位置：首页 > ops >正文

【Leetcode hot 100】21.合并两个有序链表

ops 2025/9/1 12:53:08

问题链接

21.合并两个有序链表

问题描述

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

示例 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 均按非递减顺序排列

问题解答

合并两个有序链表的核心思路是利用链表的有序性，通过比较两个链表当前节点的值，逐步构建新的有序链表。主要有两种实现方式：迭代法和递归法。

方法一：迭代法

思路

哨兵节点（Dummy Node）：创建一个虚拟头节点（哨兵），用于简化边界情况（如其中一个链表为空时的处理），避免单独判断头节点。
双指针遍历：使用一个指针（current）指向当前构建的新链表的尾部，同时遍历两个输入链表（list1 和 list2）。
比较与拼接：每次比较 list1 和 list2 的当前节点值，将较小的节点接到 current 后面，然后移动相应的指针（被选中的链表指针和 current 指针）。
处理剩余节点：当其中一个链表遍历完毕后，将另一个链表的剩余部分直接接到新链表尾部。

代码实现

/*** 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) {// 哨兵节点，简化头节点处理ListNode dummy = new ListNode(-1);ListNode current = dummy; // 当前指针，指向新链表的尾部// 遍历两个链表，比较并拼接较小的节点while (list1 != null && list2 != null) {if (list1.val <= list2.val) {current.next = list1; // 拼接list1的当前节点list1 = list1.next;   // 移动list1指针} else {current.next = list2; // 拼接list2的当前节点list2 = list2.next;   // 移动list2指针}current = current.next; // 移动current指针}// 拼接剩余节点（其中一个链表已遍历完毕）current.next = list1 == null ? list2 : list1;return dummy.next; // 哨兵节点的下一个节点才是新链表的头}
}

复杂度分析

时间复杂度：O(m + n)，其中 m 和 n 分别是两个链表的长度。需遍历两个链表的所有节点。
空间复杂度：O(1)，仅使用常数个额外指针（哨兵节点和 current 指针）。

方法二：递归法

思路
递归的核心是“缩小问题规模”：

终止条件：若其中一个链表为空，直接返回另一个链表（剩余节点无需比较，直接拼接）。
递归逻辑：比较两个链表的当前节点值，选择较小的节点作为新链表的当前节点，然后递归处理该节点的下一个节点与另一个链表的剩余部分。

代码实现

/*** 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;if (list2 == null) return list1;// 选择较小的节点作为当前节点，递归处理剩余部分if (list1.val < list2.val) {list1.next = mergeTwoLists(list1.next, list2);return list1;} else {list2.next = mergeTwoLists(list1, list2.next);return list2;}}
}