【刷题日记】LeetCode 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. 递归法：代码简洁，但递归深度受链表长度限制，空间复杂度为 O(m+n)
2. 迭代法：空间复杂度更优，仅需常数级额外空间

本文采用迭代法，核心思路如下：

1. 创建哑节点（虚拟头节点），其 next 指针将指向合并后的链表头
2. 同时遍历两个链表，比较当前节点的值
3. 将较小值的节点接入结果链表尾部
4. 移动对应链表的指针继续比较
5. 当某链表遍历完毕时，将另一链表的剩余部分直接拼接至尾部

使用哑节点可避免对头节点为空的特殊处理，使代码更统一简洁。

解题步骤

1. 初始化哨兵节点：dummy = ListNode()，作为合并链表的虚拟头节点
2. 维护尾指针：tail = dummy，始终指向合并链表的末尾
3. 循环比较：
   • 当list1和list2均非空时：
     • 若list1.val ≤ list2.val，将list1接入尾部并后移指针
     • 否则，将list2接入尾部并后移指针
   • 每次操作后，tail指针后移一位
4. 处理剩余节点：将未遍历完的链表直接接至tail.next
5. 返回结果：dummy.next即为合并后的有序链表