LeetCode 1669. 合并两个链表

2026-02-02 HGNULB 约 8 分钟

文章信息 8 个分类 1 个标签

分类

题目描述

✅ 1669. 合并两个链表

题意分析

手上有两条单链表。要把 list1 中下标从 a 到 b 的这一段整体摘掉，再把完整的 list2 塞进这个空位，最后返回改造后的 list1。

约束里有两个信号非常关键。第一，1 <= a <= b < list1.length - 1，这说明被删区间既不会从头开始，也不会顶到末尾——a 前面一定还有节点，b 后面也一定还有节点。换句话说，两个拼接端点都保证存在，不需要处理「接到表头」这种要用哨兵才好写的情况。第二，list2 保证非空，所以不会出现「插入一段空链表、要把两侧直接连起来」的退化分支。

再看目标本身：题目要的是节点层面的重接，不是值的复制。链表的形状完全由指针决定，所以整件事的实质是「改哪几个 next」，而不是「造一条新链」。

边界上要额外留意下标语义：a 和 b 都是从 0 开始计数的闭区间端点，a 等于 b 时表示只删一个节点，这是完全合法的输入。

解法：定位前驱和后继后拼接

核心思路

先想最笨的办法：把 list1 全部读进数组，按下标切片重组，再重新串成链表。这当然能过，但白白付出了 $O(n)$ 的额外空间，而且新建了一堆节点。瓶颈在于，我们其实一个值都不需要读，只是被数组这种随机访问结构的思维带偏了。

换个角度看这个操作：删掉一段、插入一段，链表的整体结构只在两处发生变化——被删区间的前边界和后边界。区间内部那些节点的 next 指向什么已经无所谓了，它们从此不可达。

于是问题被压缩成「找到两个锚点、改两条边」。设 preA 是下标 a - 1 的节点，afterB 是下标 b + 1 的节点，tail 是 list2 的最后一个节点。

不变量是：改造完成后，preA.next 必须指向 list2 的头，tail.next 必须指向 afterB，其余所有节点的 next 保持不变。 只要这两条边接对，整条链就是 list1[0..a-1] + list2 + list1[b+1..]，正是答案。全过程零额外节点、零数据拷贝。

解题步骤

从 list1 出发走 a - 1 步得到 preA。因为下标从 0 起算，头节点已经是下标 0，所以到下标 a - 1 只需走 a - 1 步；约束保证 a >= 1，这一步永远不会走空。

从 preA 继续往后走，直到停在下标 b + 1 的节点，把它记作 afterB。这一步必须在修改任何指针之前完成，否则一旦 preA.next 被改掉，通往区间后半段的唯一通路就断了，afterB 再也找不回来。

从 list2 头部一直走到 next 为空，得到 tail。之所以要单独扫一遍，是因为单链表没有尾指针，接回后半段必须先知道尾巴在哪。

令 preA.next = list2，完成前半段与新链的对接。

令 tail.next = afterB，完成新链与后半段的对接。两步顺序可以互换，因为它们操作的是两个互不相干的节点，但都必须晚于 afterB 的定位。

返回 list1。头节点从未被修改，所以原引用仍然是整条结果链的入口。

以 list1 = [10,1,13,6,9,5]、a = 3、b = 4、list2 = [1000000,1000001,1000002] 走一遍：先定位 preA，从 10 出发走 a - 1 = 2 步，依次经过 1、到达 13，所以 preA 是下标 2 的节点 13。接着从 preA 继续走，循环变量从 a - 1 = 2 递增到 b = 4，一共走三步：第一步到 6（下标 3），第二步到 9（下标 4），第三步到 5（下标 5），于是 afterB 是节点 5。然后扫 list2 找尾巴：从 1000000 走到 1000001，再走到 1000002，此时 next 为空，tail 就是 1000002。最后接两条边：13.next 从原来的 6 改成 1000000，1000002.next 从空改成 5。沿着 list1 重新读一遍得到 10 → 1 → 13 → 1000000 → 1000001 → 1000002 → 5，被摘掉的 6 和 9 已经不可达，与预期输出一致。

代码实现

class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode preA = list1;
        for (int i = 0; i < a - 1; i++) {
            preA = preA.next;
        }

        ListNode cur = preA;
        for (int i = a - 1; i <= b; i++) {
            cur = cur.next;
        }
        ListNode afterB = cur;

        ListNode tail = list2;
        while (tail.next != null) {
            tail = tail.next;
        }

        // 删除 [a,b] 后，用 list2 的首尾分别接住两侧链表。
        preA.next = list2;
        tail.next = afterB;

        return list1;
    }
}

func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
    preA := list1
    for i := 0; i < a-1; i++ {
        preA = preA.Next
    }

    cur := preA
    for i := a - 1; i <= b; i++ {
        cur = cur.Next
    }
    afterB := cur

    tail := list2
    for tail.Next != nil {
        tail = tail.Next
    }

    // 删除 [a,b] 后，用 list2 的首尾分别接住两侧链表。
    preA.Next = list2
    tail.Next = afterB

    return list1
}

复杂度分析

时间复杂度：$O(n + m)$，其中 $n$ 是 list1 长度、$m$ 是 list2 长度。定位两个锚点最多把 list1 从头扫到下标 b + 1，找尾节点把 list2 整体扫一遍，之后只有常数次指针赋值。

空间复杂度：$O(1)$，全程只用了 preA、cur、afterB、tail 四个指针变量，没有创建任何新节点或辅助容器。

关键点总结

链表的区间替换本质是「改两条边」。想清楚哪两条边、以及它们的两个端点分别是谁，代码就只剩下定位工作，这个视角可以直接迁移到区间反转、区间删除、区间旋转等一整类题。

修改指针之前必须先把所有还要用到的引用抓在手里。链表是单向的，一旦某条边被覆盖，它后面的部分就不可达了，这是链表题最常见的失手点。

单链表拿不到尾节点，只能线性扫。凡是需要「把某条链接回主干」的题，都要预留一次找尾的遍历，或者在维护结构时顺带记录尾指针。

题目给的下标约束往往在暗示需不需要哨兵节点。这题保证了 a >= 1，所以 preA 一定存在，不需要虚拟头；如果约束放宽到 a 可以为 0，第一件事就应该是加 dummy。

面试视角：主动指出「用数组重建也能做，但空间是 $O(n)$ 且新建节点」，再给出 $O(1)$ 的原地指针版本，能展示对链表数据结构特性的理解，而不只是会写循环。

面试视角：常被追问「如果 list2 可能为空怎么办」。答案是先判空，直接令 preA.next = afterB 即可；主动补上这个分支比等面试官提醒更好。

易错点总结

错误写法：先执行 preA.next = list2，之后再去找 afterB。用例 list1 = [0,1,2,3,4,5]、a = 3、b = 4、list2 = [100] → 从 preA 往后已经走进了 list2，list2 长度不足时直接空指针，长度足够时会取到 list2 内部的节点，结果链彻底错乱。

错误写法：定位 preA 时走了 a 步而不是 a - 1 步。用例 list1 = [10,1,13,6,9,5]、a = 3、b = 4 → preA 落到下标 3 的节点 6，结果保留了本应删除的 6，输出多出一个节点。

错误写法：把 afterB 取成下标 b 的节点。用例同上、b = 4 → afterB 是节点 9，它本属于删除区间，最终链变成 10 → 1 → 13 → 1000000 → 1000001 → 1000002 → 9 → 5，多了一个 9。

错误写法：忘记接 tail.next = afterB，只做了前半段拼接。用例 list1 = [10,1,13,6,9,5]、a = 3、b = 4、list2 = [100,101] → 结果变成 10 → 1 → 13 → 100 → 101，原链表尾部的 5 被整段丢失。

错误写法：找 list2 尾节点的循环写成 while (tail != null) tail = tail.next。用例任意非空 list2 → 循环结束时 tail 已经是空指针，紧接着的 tail.next = afterB 直接抛空指针异常。

错误写法：返回 preA 或返回 list2 而不是 list1。用例 a = 3 的任意输入 → 返回值丢掉了区间之前的所有节点，只剩下从拼接点开始的后半条链。

错误写法：认为 a == b 是非法输入并特判返回原链。用例 list1 = [0,1,2,3,4]、a = 2、b = 2、list2 = [9] → 这其实是合法的「只删一个节点」，特判后应得的 0 → 1 → 9 → 3 → 4 变成了未修改的原链。

错误写法：用两个独立的循环分别从表头走到 a - 1 和从表头走到 b + 1，却把第二个循环的步数写成 b。用例 a = 1、b = 1 → afterB 取成了下标 1 的节点，也就是要删的那个，删除操作等于没生效。

错误写法：把 list2 的节点值逐个复制到 list1 对应位置上，而不改指针。用例 list1 = [0,1,2,3,4,5]、a = 3、b = 4、list2 = [7,8,9] → 待插入长度与被删长度不同，位置根本对不上，结果既不完整也不正确。

相似题目

题目	难度	考察点
92. 反转链表 II	中等	同样锁定区间前驱与后继，但区间内要就地反转
203. 移除链表元素	简单	按值删除且可能删到头节点，需要哨兵节点
82. 删除排序链表中的重复元素 II	中等	删除区间由重复值动态决定，边界需边扫边定
86. 分隔链表	中等	拆成两条子链再首尾相接，考察尾指针维护
61. 旋转链表	中等	先成环再断环，断点位置由取模计算得到
21. 合并两个有序链表	简单	按值交替穿插两条链，而非整段替换