合并两个有序链表

一、题目（LeetCode 21 · 简单 · Hot100）

将两个升序链表合并为一个新的升序链表并返回。新链表由拼接给定的两个链表的所有节点组成。

输入：l1 = 1 -> 2 -> 4, l2 = 1 -> 3 -> 4
输出：1 -> 1 -> 2 -> 3 -> 4 -> 4

二、思路演进

2.1 暴力：扔掉"已有序"这个前置条件

把两条链的值全收进数组，排序后重建链表——O((m+n) log(m+n))。这比应有效果多付一个 log 因子，因为**"两条各自有序"的信息被完全浪费**。另一个朴素写法是"每次找较小的头插到结果尾部，但每次从头找尾"——没记住 tail，退化 O(n²)。

2.2 关键洞察：哑结点 + tail，归并逐段前移

有序性保证：结果的下一个节点必然是两条链当前头部中较小的那个。于是：

• dummy 哑结点固定结果头部（空头），tail 记录结果当前的尾；
• 两指针 l1、l2 指向各链剩余部分的头，取小者接到 tail 后，该指针前移；
• 一条链耗尽后，另一条剩余链整条接上（已有序，无需再动）。

每个节点只被访问一次，"已有序"被利用到极致。

2.3 与数组版的镜像对比

库内旧文 合并两个有序数组 是同一思想的数组版，方向却相反。数组从后往前：尾部有预留空间，且后向前填充避免整体挪动。链表从前往后：插入是 O(1)，根本没有挪动成本。方向选择由存储结构决定——这是面试讲双指针时的加分点。

三、复杂度分析

• 时间 O(m + n)：每轮循环淘汰一个节点，共 m + n 轮，每轮 O(1)。
• 空间 O(1)：只重排已有节点，不新建（递归版除外）。

四、代码

package org.example;

/**
 * @author MUYI
 * @version 1.0
 * @date 2026/10/17
 */
public class LeetCode_21 {

    public static void main(String[] args) {
        ListNode l1 = build(new int[]{1, 2, 4});
        ListNode l2 = build(new int[]{1, 3, 4});
        ListNode node = mergeTwoLists(l1, l2);
        while (node != null) {              // 期望输出 1 1 2 3 4 4
            System.out.print(node.val + " ");
            node = node.next;
        }
    }

    /** 迭代版：哑结点定头、tail 记尾、两指针取小者接上 */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);   // 哑结点：省掉"结果头是谁"的特判
        ListNode tail  = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {         // 相等取 l1，保持稳定
                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;
    }

    /** 递归版：写法最短，但长链栈深 */
    public static ListNode mergeRecursive(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val <= l2.val) {
            l1.next = mergeRecursive(l1.next, l2);
            return l1;
        }
        l2.next = mergeRecursive(l1, l2.next);
        return l2;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    static ListNode build(int[] values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

}

五、坑点

• 不用哑结点就要为"结果的第一个节点来自哪条链"写 if/else 特判，且循环里还得判结果链是否为空。代价：逻辑翻倍、错一处的概率翻倍。
• 循环后忘记接剩余链：剩的那条已有序，tail.next = 剩余头 一步完成，逐个复制是画蛇添足。
• 递归版在长链上栈溢出：10^4 ~ 10^5 节点量级就会触及默认栈深，生产代码选迭代。同族递归陷阱见 反转链表。
• 比较方向：升序输入取小者；有人手滑写成取大者，示例对但排序方向反。
• 相等时取 l1 还是 l2 结果值相同，取 l1 保持归并稳定性——被追问稳定性时要答得上来。

六、变形追问

• 变体一（合并 K 个升序链表，LeetCode 23，Hot100）：两条两两顺序合并是 O(kN)。进阶是小根堆或分治两两合并。小根堆：堆里放 k 条链当前头，每轮弹最小接上再压它的 next，O(N log k)。分治两两合并：同复杂度，且可以复用本题函数。
• 变体二（追问）："两条链分别是升序和降序，怎么合并？"——先把降序那条反转链表成升序，再走本模板。考察的是"先归一化输入形态再套用标准过程"的意识。相关练习：排序链表 LeetCode 148，找中点 + 反转 + 归并。

2026-10 新增（E 轨 · Hot100 第一批）。