好的，我们这次来详细讲解 LeetCode 第 21 题「合并两个有序链表」。
这道题是链表操作中的经典入门题，也是很多复杂问题的基础。

1. 题目描述

题目链接：
https://leetcode.com/problems/merge-two-sorted-lists/

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

示例：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

输入：l1 = [], l2 = []
输出：[]

输入：l1 = [], l2 = [0]
输出：[0]

链表节点定义（题目已给）：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

2. 思路分析

2.1 核心任务

• 两个链表都是 非递减顺序。
• 合并后的链表也要保持非递减顺序。
• 不能创建新节点，而是通过改变 next 指针来连接已有节点。

2.2 基本思路

我们可以用类似 归并排序 中合并两个有序数组的方法，但链表的好处是不需要额外空间来存储合并结果，只需要调整指针。

步骤：

1. 创建一个 哑节点（dummy node） 作为新链表的起始前驱，这样可以避免处理空链表的特殊情况。
2. 用一个 current 指针指向新链表的当前末尾。
3. 比较 l1 和 l2 当前节点的值，将较小的节点接到 current 后面，然后移动相应的链表指针和 current 指针。
4. 当其中一个链表遍历完后，将另一个链表的剩余部分直接接在新链表末尾。
5. 返回 dummy.next，即新链表的真正头节点。

3. 详细步骤演示

以 l1 = [1,2,4], l2 = [1,3,4] 为例：

初始状态：

l1: 1 -> 2 -> 4
l2: 1 -> 3 -> 4
dummy: 0
current: dummy

第 1 步：比较 l1.val(1) 和 l2.val(1)，相等时通常取 l1（或 l2 都可以，这里取 l1）。

current.next = l1
l1 = l1.next
current = current.next

此时新链表：dummy -> 1 (l1 的 1)

第 2 步：l1 现在指向 2，l2 指向 1，比较：l2.val(1) < l1.val(2)

current.next = l2
l2 = l2.next
current = current.next

新链表：dummy -> 1 (l1) -> 1 (l2)

第 3 步：l1 指向 2，l2 指向 3，比较：l1.val(2) < l2.val(3)

current.next = l1
l1 = l1.next
current = current.next

新链表：dummy -> 1 -> 1 -> 2

第 4 步：l1 指向 4，l2 指向 3，比较：l2.val(3) < l1.val(4)

current.next = l2
l2 = l2.next
current = current.next

新链表：dummy -> 1 -> 1 -> 2 -> 3

第 5 步：l1 指向 4，l2 指向 4，比较相等，取 l1

current.next = l1
l1 = l1.next (l1 变为 None)
current = current.next

新链表：dummy -> 1 -> 1 -> 2 -> 3 -> 4

第 6 步：l1 为空，将 l2 剩余部分（4）接上

current.next = l2

新链表：dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4

返回 dummy.next 指向的第一个节点 1。

4. 代码实现（Python）

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)  # 哑节点
    current = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    # 接上剩余的链表
    if l1:
        current.next = l1
    else:
        current.next = l2
    
    return dummy.next

5. 复杂度分析

• 时间复杂度：O(m + n)，其中 m 和 n 分别是两个链表的长度。每次循环会处理一个节点，直到两个链表都遍历完。
• 空间复杂度：O(1)，只使用了几个指针变量，没有使用额外空间。

6. 边界情况考虑

• 一个链表为空，另一个非空：直接返回非空链表。
• 两个都为空：返回空。
• 链表中有重复值：比较时 <= 保证稳定顺序（先取 l1 的重复值）。

7. 总结

这道题是链表操作的基础，关键在于：

1. 使用 哑节点 简化头节点处理。
2. 使用 current 指针逐步构建新链表。
3. 最后直接连接剩余链表，无需循环追加。

这个方法是最高效的，也是面试中最常要求的写法。
理解后可以尝试类似题目，比如合并 k 个有序链表（LeetCode 23 题），就是本题的扩展。