【中等】题解力扣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 均按 非递减顺序 排列

解题思路

1. 迭代法：使用哑节点（dummy node）简化链表操作，避免处理头节点为空的边界情况。
2. 双指针遍历：同时遍历两个链表，比较当前节点的值：
   • 将较小值的节点链接到新链表。
   • 移动较小值节点所在链表的指针。
3. 拼接剩余节点：当其中一个链表遍历完成后，将另一个链表的剩余部分直接链接到新链表末尾。
4. 空间优化：直接复用原链表节点，不创建新节点，空间复杂度为 O(1)。

代码实现（Java版）

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dummy = new ListNode(0); // 哑节点简化操作ListNode cur = dummy;while (list1 != null && list2 != null) {if (list1.val <= list2.val) {cur.next = list1;  // 直接复用list1节点list1 = list1.next;} else {cur.next = list2;  // 直接复用list2节点list2 = list2.next;}cur = cur.next;}// 拼接剩余链表cur.next = (list1 != null) ? list1 : list2;return dummy.next;}
}

代码说明

1. 哑节点（dummy）：

• 初始化一个值为0的节点，其next指向新链表的头节点。
• 避免处理空链表时的边界条件，使代码更简洁。

2. 循环比较：

• 当list1和list2均非空时，比较当前节点值。
• 将较小值节点链接到cur.next，并移动对应链表的指针。

3. 剩余链表处理：

• 循环结束后，其中一个链表可能还有剩余节点。
• 通过三元运算符直接将剩余链表链接到新链表末尾。

4. 返回值：

• dummy.next指向新链表的实际头节点，直接返回即可。

提交详情（执行用时、内存消耗）