好的，我们这次来详细讲解 LeetCode 第 21 题「合并两个有序链表」。
这道题是链表操作中的基础题，也是很多复杂问题的基础，我会从题意、思路、步骤、代码到复杂度分析，一步步拆开讲清楚。

1. 题目描述

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

示例：

输入：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. 题意理解

• 两个链表 l1 和 l2 都是 非递减顺序（升序）排列的。
• 我们要把它们合并成一个新的升序链表。
• 不能创建新节点，而是直接改变 next 指针，利用原有节点。
• 类似归并排序中的 merge 步骤。

3. 思路分析

我们可以用双指针法（这里指针指的是链表节点的引用/指针）：

1. 创建一个 哑节点（dummy node） 作为新链表的起始前驱，这样可以避免处理空链表的特殊情况。
2. 用一个 tail 指针指向新链表的当前末尾。
3. 比较 l1 和 l2 当前节点的值，将较小的节点接在 tail 后面，然后对应链表的指针后移一位。
4. 重复步骤 3，直到某个链表为空。
5. 将剩余非空链表直接接在新链表末尾。
6. 返回 dummy.next。

4. 详细步骤举例

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

初始：

l1: 1 → 2 → 4
l2: 1 → 3 → 4
dummy: 0
tail: dummy

第 1 步：比较 l1.val(1) 和 l2.val(1)，相等，选 l1 的节点（选哪个都可以）。

l1: 2 → 4
l2: 1 → 3 → 4
新链表: dummy → 1
tail: 1

第 2 步：比较 l1.val(2) 和 l2.val(1)，l2 的 1 更小，接 l2 的节点。

l1: 2 → 4
l2: 3 → 4
新链表: dummy → 1 → 1
tail: 1（第二个 1）

第 3 步：比较 l1.val(2) 和 l2.val(3)，l1 的 2 更小。

l1: 4
l2: 3 → 4
新链表: dummy → 1 → 1 → 2
tail: 2

第 4 步：比较 l1.val(4) 和 l2.val(3)，l2 的 3 更小。

l1: 4
l2: 4
新链表: dummy → 1 → 1 → 2 → 3
tail: 3

第 5 步：比较 l1.val(4) 和 l2.val(4)，相等，选 l1 的节点。

l1: null
l2: 4
新链表: dummy → 1 → 1 → 2 → 3 → 4
tail: 4

第 6 步：l1 为空，将 l2 剩余部分 (4) 接上。

新链表: dummy → 1 → 1 → 2 → 3 → 4 → 4
tail: 4（最后一个）

返回 dummy.next 即 [1,1,2,3,4,4]。

5. 代码实现（Python）

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(-1)  # 哑节点
    tail = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    
    # 接上剩余部分
    tail.next = l1 if l1 else l2
    
    return dummy.next

6. 复杂度分析

• 时间复杂度：O(m + n)，m 和 n 分别是两个链表的长度，每个节点只访问一次。
• 空间复杂度：O(1)，只用了几个指针变量，没有额外开辟与 m、n 相关的空间。

7. 总结

• 使用 哑节点 可以简化链表头部的特殊处理。
• 思路就是归并排序的 merge 过程。
• 注意最后直接链接剩余链表，不需要用循环一个个接。

这样一步步下来，你应该能清晰地理解合并两个有序链表的完整过程了。如果有哪里还不明白，我可以再进一步解释。