合并两个有序链表

问题拆解

两个升序链表 l1、l2，要拼成一个新的升序链表。因为两边都已经有序，每一步只需要比较两个表头，把更小的那个接到结果后面，然后让它往后走一格。

麻烦的是结果链表的第一个节点：它没有前驱，接第一个节点和接后面的节点得写两套逻辑。如果每次都判断“结果是不是空的”，代码会被这个边界搞得很啰嗦。

引入一个不存放数据的哨兵（dummy）节点当作结果的假头，所有真实节点都变成“接在某个节点后面”，第一个节点的特殊情况就消失了。

迭代：哨兵 + 尾指针

def mergeTwoLists(l1, l2):
    dummy = ListNode()
    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

tail 始终指向结果链表的最后一个节点，每次把较小的节点挂上去后往前移。循环结束时至少有一条链表走空，剩下那条已经是有序的尾巴，直接整段接上即可。最后返回 dummy.next，跳过那个假头。

用 <= 而不是 < 能保证相等时优先接 l1，合并是稳定的。

递归

也可以顺着定义来递归：两个头里较小的那个，它的 next 就是“剩下的部分继续合并”的结果。

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val <= l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    l2.next = mergeTwoLists(l1, l2.next)
    return l2

写法很短，但递归深度等于两链表总长，节点多时不如迭代稳。

复杂度

指标	复杂度	原因
时间	O(m + n)	每个节点被接入结果一次
空间	O(1) / O(m + n)	迭代只用哨兵与指针；递归的栈深与总长度相同

可以迁移的模式

• 链表结果需要从零构建时，先设一个 dummy 头，省掉首节点判空；
• “比较两个表头、取小的、推进”是归并排序合并步骤的原型；
• 收尾时利用“另一条已经有序”直接整段拼接，不用逐个搬。

合并两个有序结构这件事在数组、链表、外部排序里反复出现，哨兵是让代码变干净的常用手法。