如何合并两个有序链表？

简化版

用哑结点 + 双指针，像拉拉链一样：比较两个链表当前节点，谁小就把谁接到结果尾部并前进，直到某条走完，再把另一条剩下的整段接上。时间 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 = 剩下的那条 一次接上即可，省去无谓的遍历。

四、稳定性与相等处理

比较时用 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)。
追问：如果两个链表降序怎么办？ 比较方向要改成取较大者，或先反转/统一排序方向后再合并。

七、加强记忆

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

简化版

详细版