如何合并两个有序链表？

简化版

用哑结点 + 双指针，像拉拉链一样：比较两个链表当前节点，谁小就把谁接到结果尾部并前进，直到某条走完，再把另一条剩下的整段接上。时间 O(m+n)、空间 O(1)。也能递归写。

详细版

迭代法（推荐）：

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;              // tail 始终指向结果链表的最后一个
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {         // 谁小接谁
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2; // 把剩下的整段直接接上
    return dummy.next;
}

递归法：

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

递归简洁，但有 O(m+n) 的栈深度；迭代 O(1) 空间更稳。

完整版教学

一、核心是「双指针拉链」

两条链表都已经有序，所以每一步只需比较两个表头，较小的那个一定是当前应该放进结果的最小值。把它接到结果尾部、指针后移，重复这个过程，就把两条有序链表归并成一条有序链表。这正是归并排序里「merge」那一步在链表上的体现。

二、哑结点让「接第一个节点」不用特判

结果链表一开始是空的，第一个要接的节点没有前驱。用哑结点 dummy 当「假头」，tail 从 dummy 开始，接节点时统一写 tail.next = ...，不用为「第一个节点」单独判断。最后返回 dummy.next（真正的头）。

三、为什么可以「剩下的整段直接接上」

循环退出时，必有一条链表已经走完（为 null），另一条剩下的部分本身就是有序的、且都比已合并部分大，所以不用再逐个比较，直接 tail.next = 剩下的那条 一次接上即可，省去无谓的遍历。

这节要真正讲透，需要把结论落到结构变化上：在如何合并两个有序链表？里，每一步操作都会影响某个指针、索引、节点关系或辅助状态。可以主动说明“操作前满足什么不变量、操作后这个不变量如何继续成立”，再补一个 3 个节点或 5 个元素的小例子。这样读者不仅知道答案，还能自己推导同类变体。

四、稳定性与相等处理

比较时用 l1.val <= l2.val（相等时优先接 l1）可以保持稳定——相等元素保留原来的相对顺序。虽然对纯数值无所谓，但如果节点带额外信息，稳定性可能有意义，是个能加分的细节。

五、延伸：合并 K 个有序链表

合并 K 个有序链表就是这道题的推广：可以两两合并（分治，O(N·logK)），也可以用小顶堆每次取 K 个表头里最小的（O(N·logK)）。地基都是这里的「双指针拉链合并」。

场景	推荐做法	复杂度
合并两个有序链表	双指针 + dummy	O(m+n) 时间，O(1) 空间
合并 K 个有序链表	分治两两合并	O(N log K) 时间
合并 K 个且想每次取最小表头	小顶堆	O(N log K) 时间，O(K) 空间

举个例子：1→3→5 和 1→2→4 合并时，若相等时优先取第一条链表，结果顺序是第一条的 1 先进入结果，再取第二条的 1。这就是稳定性：相等元素不乱改原有相对顺序。

合并有序链表不是新建一堆节点再拷值，常见面试写法是复用原节点，只改 next 指针把它们重新串起来。

六、常见误区与追问

误区：每接一个节点都要新建节点。 通常可以复用原链表节点，只调整指针，空间 O(1)。
误区：一条链表走完后还要逐个比较剩余节点。 另一条剩余部分已经有序，且都应排在结果尾部，直接整段接上即可。
误区：dummy 是结果中的真实节点。 dummy 只是哨兵，返回时要返回 dummy.next。
追问：为什么 <= 能保持稳定？ 相等时先接左链表节点，可保留左链表中相等元素相对靠前的顺序。
追问：递归写法有什么代价？ 递归代码短，但递归深度最多 m+n，额外栈空间 O(m+n)。
追问：如果两个链表降序怎么办？ 比较方向要改成取较大者，或先反转/统一排序方向后再合并。

八、伪代码与不变量

数据结构题最好把操作过程写成伪代码，因为指针、索引或状态变化一旦说不清，就容易在边界用例上出错。以如何合并两个有序链表？为例，可以先固定不变量，再解释每一步为什么保持它。

初始化：维护结构不变量 invariant
遍历/调整：每处理 1 个节点或元素，都只改变必要指针/索引
校验：操作后结构仍满足顺序、连通性或堆/树性质
复杂度：每个元素最多进入/离开结构 O(1) 或 O(log n) 次

九、一步步推演与边界

回答如何合并两个有序链表？时，最好额外走一遍小样例。先用 3～5 个元素演示正常操作，再故意加入空结构、单元素、重复值或极端位置，观察不变量是否仍成立。比如链表题要盯住前驱、当前、后继 3 个指针；树题要说明递归返回值代表什么；堆题要说明上浮/下沉什么时候停止；图题要说明 visited 或入度数组何时更新。

这种推演的价值在于把“我知道算法”变成“我能证明边界也不会错”。很多面试失分不是主流程不会，而是少了空节点、尾节点、重复边、环、K 越界这类边界。把这些点主动讲出来，既能减少代码 bug，也能让复杂度分析更可信。

边界类型	检查方式	容易出错的地方
空结构	输入为空或 root/head 为 null	直接访问属性导致异常
单元素	只有 1 个节点或元素	前驱/后继、左右子树判断错误
重复值	多个元素相等	比较条件写成 < 还是 <=
极端位置	头尾、最大最小、第一层最后一层	更新指针或索引越界

补充边界演练

为了把如何合并两个有序链表？真正讲透，可以再补一组边界演练。第一组是空结构或空输入，用来确认代码不会在访问 head、root、stack top 或队首时崩溃；第二组是单元素，用来确认循环条件不会多走一步；第三组是 2～3 个元素的最小非平凡样例，用来观察指针、栈、队列或 visited 状态如何变化。

如果是树遍历题，就画出 root、left、right 三个节点，逐步记录栈里元素的进出；如果是图遍历题，就用 4 个点、4 条边验证 BFS 的层次性和 DFS 的路径性；如果是链表题，就把 pre、cur、next 三个指针写在纸上，每移动一次都检查链是否断开。面试时把这个过程讲出来，比单纯写出最终代码更能说明你真的理解结构变化。

边界 1：空输入 -> 直接返回，不访问节点属性
边界 2：单元素 -> 循环最多处理 1 次，结果保持合法
边界 3：三个元素 -> 手动跟踪每一步状态变化
验证目标：不变量始终成立，且每个节点/元素被处理次数可解释

七、加强记忆

合并两个有序链表 = 哑结点 + 双指针拉链：比较两个表头、谁小接谁、指针后移，一条走完就把另一条剩余整段接上，返回 dummy.next。时间 O(m+n)，迭代 O(1) 空间。

简化版

详细版