LeetCode 21. 合并两个有序链表：链表合并与「虚拟头节点」

题目与「归并 merge」的链表版

LeetCode 21：合并两个升序链表为一个升序链表——返回合并后的头节点。

输入：1 → 2 → 4 和 1 → 3 → 4
输出：1 → 1 → 2 → 3 → 4 → 4

与 LeetCode 88（合并两个有序数组）的对比：数组的合并（原地、从后往前、尾部有预留——「数组的约束」是「空间 O(1)」；链表的合并（「节点的重接」——不需要复制数据——「链表的天然优势」：改变 next 指针即完成合并——「无需额外空间」——「链表版反而是更简单的版本」——两道题的对照：「数据结构的物理形态决定算法的形态」——数组的连续存储限制重排、链表的指针自由重接——「链表版是数组版的镜像教学」。

解法：dummy 节点 + 尾插

dummy 节点的作用：合并的第一个节点来自 l1 还是 l2——「头节点的特判」：没有 dummy 时要先判断谁小、确定新头——「dummy 消除特判」：虚拟头挂在最前面，所有节点统一「尾插」到 dummy 链——「结果头 = dummy.next」——「dummy 是链表题的第一神器（LRU 篇的哨兵同源——「虚拟头/哨兵」家族：消除头部特判——「特判的消除」=「代码的简化」——**「设计题与算法题都受益」。

def merge_two_lists(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 or l2        # 剩余整段直接拼接
    return dummy.next           # 真头

「尾指针 tail」的维护：「tail 永远指向结果链的最后一个节点」——每次接一个节点、tail 后移——「tail.next = 选中节点」+「tail = tail.next」——两步的顺序（先接、后移——「尾插法」的固定动作——「tail 的角色」：写指针（「写指针」概念在链表的形态——与数组的写指针（原地合并篇）同族——「尾插」与「头插」的对比：头插会「颠倒顺序」（反转链表篇的头插——合并要保序——「保序用尾插、逆序用头插」——「插入位置决定结果顺序」**。

「剩余直接拼接」的红利：循环结束时（一个链表用完）——「剩余的部分已经是排好序的」——直接 tail.next = l1 or l2 拼接——「不需要逐个接」——「有序的剩余 = 直接链接」——「这是合并比排序便宜的地方」——归并排序的 merge 复杂度 O(m+n)——「剩余拼接」是 merge 实现的最优收尾——「Python 的 or 技巧」（l1 or l2——非 None 的那个——**「简洁但可读性」的权衡——面试时写 tail.next = l1 if l1 else l2 更清晰。

递归解与「合并 K 个链表」的地位

递归版的优雅：「合并两个链表的递归」：

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

「递归版的直觉」：「两个头谁小，谁就是合并后的头——剩下的交给递归」——「一行递归完成剩余」——「递归版的简洁」与「迭代版的效率」——递归 O(m+n) 栈空间——「同反转链表篇的取舍」——**「面试双解法」的标准动作。

「合并 K 个升序链表」的地位（LeetCode 23，库内已有专文）：「两两合并」：依次两两合并（O(k·N)——「分治合并」：两两配对递归（O(N·log k)——「本题是 23 题的原子操作」——「21 → 23」的升级路径——「23 的两个解法（堆 vs 分治）都建立在 21 之上」——「基础题是难题的零件」——「分治合并」的图示（两两配对、层层归并——「归并排序的树形」——与归并排序的合并结构完全同构——「链表的归并」**。

合并两个有序链表的进阶：dummy 家族与「链表题的设计模式」

合并两个有序链表的进阶：dummy 家族的系统梳理与链表题的设计模式。「dummy 家族的完整形态」：「形态一：单向 dummy」——虚拟头节点——「单向 dummy 的适用」（单向链表——「消除头部特判」——删除、合并、反转、「头部操作」——「形态二：双向双哨兵」——头哨兵+尾哨兵——「双向链表的完全体」（LRU——「双向哨兵」的消除范围（头尾特判全消——「形态三：环形哨兵」——哨兵自连成环——「环形」的边界消除（空链表也是环（哨兵自指——「环形哨兵」的极简——「三种形态」的递进——「形态的选择」按需求——「单向够用就不双向」——「按需升级」。「链表题的设计模式」：「模式一：dummy+tail 尾插」——合并、排序、建链——「尾插的固定五行」（dummy=ListNode(); tail=dummy; ...; tail.next=x; return dummy.next——「五行的肌肉记忆」——「尾插」的适用（保序——「尾插」的合并、建链、「模式二：头插」——反转——「头插逆序」——「模式三：快慢指针」——判环、找中——「模式四：多指针重接」——分组翻转、区间反转——「四种模式」覆盖大部分链表题——「模式的选择」由操作决定——「合并用尾插、反转用头插、判环用快慢」——「模式匹配」——「面试的快速定位」——「识别模式 → 套用模板 → 调整细节」——「识别」是关键——「识别」靠刷题的积累——「积累」的效率取决于「模式化学习」——「每个模式亲手写三遍」——「三遍」形成肌肉记忆——「肌肉记忆」在面试压力下的可靠。「合并 K 个链表」的分治地位：「23 题的三种解法」：顺序合并（O(kN)——「顺序的累积」（每次合并把结果与下一个合并——「后面的合并越来越大」——「分治合并」（两两配对、层层归并——「分治的树形」——「归并排序的树形」——「O(N log k)」——「堆」（PriorityQueue——「堆的 O(N log k)」——「堆 vs 分治」——「堆更通用、分治更优雅」——「三种解法」——「21 是所有解法的原子操作」——「合并两个有序链表」的精熟直接决定 23 的得分——「基础决定上限」。合并两个有序链表的进阶总结：dummy 家族的三形态（单向/双向双哨兵/环形）+链表四模式（尾插/头插/快慢/多指针）+23 的三种解法（顺序/分治/堆——21 是原子操作）——「合并两个有序链表」的教学价值：它同时训练了「dummy 的使用」「尾插的肌肉记忆」「递归的信任」「分治的直觉」——「一个 Easy 题四个思想」——「这就是为什么 Easy 题也要认真做」——「Easy 题的深度」在于思想的密度——「思想密度」高的 Easy 题，比「思想密度低的 Hard 题」更有学习价值**。

多路归并的现实舞台：外部排序、Feed 流与惰性合并

把 21 题放到更大的坐标系里，它只是「归并家族」里 k=2 的最小情形，而 k 路归并才是生产环境的常客。「外部排序」：内存装不下的 100GB 日志要排序，标准做法是分块——每次读 1GB 进内存排序后落盘成一个有序段，得到 100 个有序段，再用 k 路归并合成一个：k 个段各维护一个读指针，每轮在 k 个当前头部元素里取最小的写入输出——这正是本题「比较两个头、小的进结果」的 k 路推广，比较 k 个头用小顶堆维护，总代价 O(N log k)；数据库的大排序、搜索引擎的段合并、日志系统的压缩，内核全是这套「分块有序 + 多路归并」。「Feed 流的时间线合并」：用户关注了 500 个人，拉时间线时不可能把 500 份列表全量排序——把每个人的最新内容看成按时间倒序的有序流，取前 k 个来源的「头部」做归并，翻页时继续从各流取下一批——堆维护各流当前游标，heapq.merge 就是这个动作的现成实现；社交时间线、聚合资讯流、多仓库的 git log 按时间合并，都是同一招。「惰性合并」是链表版独有的红利：数组归并要求两个输入「已经全部就位」，而链表（以及一切迭代器、生成器）可以边生产边消费——merge 函数只盯着两个头节点，根本不关心后面还有多长，甚至可以是无限流——这个性质让合并成了流式系统的基本算子：消息队列的多分区消费、监控数据的多源汇聚，都是「指针在两个（k 个）有序流上交替前进」的形态。呼应正文的一道追问：为什么 88 题合并两个有序数组要从后往前、链表却不用？——数组原地合并的困境是「输出区与输入区重叠」，从前往后写会覆盖还没比较的元素，所以从尾部倒着写；链表的重接不搬数据、不存在覆盖问题，从头正着写即可——「从后往前」不是归并的通用规则，是数组空间约束下的特解。最后留个手练：把本题的迭代版扩成 k 路版（堆维护 k 个头），写完你会发现合并 K 个链表（23 题）已经解决了一大半——基础题的利息，就在这种「顺手升级」里兑现。

「为什么比较时用 <= 而不是 <？」——<= 让值相等时优先接 l1 的节点——这是稳定性：相等元素保持原有先后次序。对纯数字链表看不出差别，但元素若是「按时间戳排序的日志记录」，同秒的记录先后有意义，稳定合并才不会重排历史——归并排序正是靠每一层 merge 的稳定性，才成为「稳定 + O(n log n)」的代表。顺带的追问「链表排序为什么偏爱归并」：快速排序的优势（随机访问、原地分区）在链表上全部失效，而链表归并的两个零件——快慢找中点、本题的 merge——恰好都是链表最擅长的指针操作，所以链表排序的标准答案就是归并——数据结构的物理性质再次决定算法的选择。

小结

合并两个有序链表的完整解析：dummy 的消除特判（虚拟头+尾指针——「tail 永远指向结果链尾」——「尾插保序、头插逆序」）；剩余直接拼接（有序剩余整段接——「merge 比排序便宜」）；递归的直觉（谁小谁当头、剩余交递归——「栈空间」的代价——迭代与递归双解）；地位（21 是 23 的原子操作——堆与分治都建立在它之上——「归并树形」的同构）。给学习者的建议：dummy/tail 的写法练到条件反射——「dummy = ListNode(); tail = dummy; ...; return dummy.next」这五行是链表合并类题目的固定开场——「开场五行写完，题目就只剩比较逻辑」——以及，「链表的合并」之所以简单于数组，本质是「指针的重接 vs 数据的搬运」——数据结构的物理性质决定算法的形态——这句话在本题与 88 题的对照中得到了完美体现**。

合并两个有序链表看似简单，却是「dummy 节点」「尾插法」「归并合并」「分治结构」四个思想的交汇点——Easy 题里藏着分治算法的地基。