21. 合并两个有序链表

Origin: LeetCode 21

题目描述

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

示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

示例 2： 输入：l1 = [], l2 = [] 输出：[]

示例 3： 输入：l1 = [], l2 = [0] 输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

我的解法（对偶插入式）

不用 dummy 空节点，直接让值小的那条链当”主链”（cur），另一条当 other 往里插。

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    if (!list1) return list2;
    if (!list2) return list1;
    const dummy = new ListNode(0);
    dummy.next = list1.val < list2.val ? list1 : list2
    let cur = dummy.next
    let other: ListNode | null = dummy.next === list1 ? list2 : list1
    while (cur.next && other) {
        if (cur.next && other && cur.next.val >= other.val) {
            const temp = cur.next
            const otherTemp: ListNode | null = other.next
            cur.next = other
            other.next = temp
            cur = cur.next
            other = otherTemp
        }
        if (cur.next && other && cur.next.val < other.val) {
            cur = cur.next
        }
    }
    if (other) {
        cur.next = other
    }
    return dummy.next
};

思路：

1. 比较两个链表头，值小的当主链，主链头作为结果起点
2. cur 沿主链走，other 是待插入链的当前节点
3. 当 cur.next.val >= other.val 时，把 other 插到 cur 后面（经典三指针交换：temp 暂存 cur.next，other.next 接回 temp，cur 前进到 other，other 前进到原来的 other.next）
4. 否则 cur 直接前进
5. 循环结束后 other 若有剩余，整段接到 cur 后面

边界用例验证过 6 组：常规合并、list2 更长、list1 更长、头部插入 [5]+[1,2,3]、全相等 [1,1,1]+[1,1]、单节点逆序 [2]+[1]，全部通过。

标准解法（dummy 归并）

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummy = new ListNode()
    let cur = dummy
    while (l1 && l2) {
        if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next }
        else { cur.next = l2; l2 = l2.next }
        cur = cur.next
    }
    cur.next = l1 ?? l2   // 剩下的直接整段接上
    return dummy.next
}

两种解法对比

	我的解法	标准解法
行数	~20 行	7 行
核心	other 往主链里”插”，指针交换	每次摘一个节点”接”到 dummy 后
特殊情况	头节点选择、尾部剩余需单独处理	无，dummy 统一处理
可读性	要维护 cur/other 对应关系，读者需转弯	单向推进，一目了然

我的解法聪明在省掉了 dummy——但省的方式是引入了”主链/插入链”的对偶概念，代价是初始化和收尾都要多写逻辑。dummy 节点的本质作用就是消灭”第一个节点”的特殊情况，让所有节点统一处理。面试时写标准解法，dummy 模式的熟悉度本身就是考点。

解题思路

两个指针分别遍历两个链表，每次取较小的节点接到结果链表后面。

dummy 头节点简化处理：不需要特殊处理第一个节点。

复杂度

• 时间：O(n + m)
• 空间：O(1)

关联

• 链表解题 - 链表题型总览
• 快慢指针 - 141. 环形链表用的技巧