LeetCode 1669. 合并两个链表

约 4 分钟
文章信息 8 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节 阿里
标签
链表

题目描述

✅ 1669. 合并两个链表

image-20260928225317912

image-20260928225317913

题意分析

将第一条链表中下标从 a 到 b 的节点全部删除，再把第二条链表插入原位置。下标从零开始，删除范围包含两个端点，两条链表中保留部分的内部顺序都不改变。

这不是按数值大小归并，而是替换一整段节点。题目保证范围合法、a >= 1 且第二条链表非空，所以删除段一定有前驱，第一条链表的头节点也不会被替换。需要找到删除段两侧和第二条链表末端，完成两处连接。

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

核心思路

[!blue]

用 preA 保存第一条链表下标 a - 1 的节点，它是删除段之前最后一个保留节点；用 afterB 保存下标 b + 1 的节点，它是删除段之后仍需保留部分的入口。

从头节点出发移动 a - 1 步即可找到 preA。再从它继续移动 b - a + 2 步，越过下标 a 到 b 的全部节点并到达后继。这里比删除段长度多一步，是因为起点位于删除段之前，而终点位于删除段之后。

两侧位置必须在改写连接前保存。如果先把 preA.next 指向 list2，再沿这个指针去找原区间后继，就会走进第二条链表，失去原来定位的路线。保存好 afterB 后，再从 list2 向后找到尾节点 tail。

最后令 preA.next = list2，让前缀接上新链表的头；再令 tail.next = afterB，让新链表尾部接回原后缀。被删除区间不再从返回链表中可达，其余节点和第二条链表的内部连接均保留，因此无需复制节点。

解题步骤

  1. 从 list1 头节点前进 a - 1 步，定位删除段前驱 preA。
  2. 从 preA 再前进 b - a + 2 步，保存删除段后继 afterB。
  3. 从 list2 头部找到尾节点 tail。
  4. 设置 preA.next = list2 和 tail.next = afterB，完成两侧拼接。
  5. 返回原 list1 头节点。

代码实现

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、m 为两条链表长度。
  • 空间复杂度：$O(1)$，复用原节点。

关键点总结

[!green]

  • 删除范围包含 a 和 b，共 b−a+1 个节点。
  • 需要同时保存接入前后的连接点。

易错点总结

[!yellow]

  • 少走一步会把 b 位置节点保留下来。
  • 只接入第二条链表头而不接尾，会丢失原链表后半段。
  • 先覆盖前驱后再沿其 next 寻找原后继，会走入 list2。

相似题目

题目 难度 关联与区别
92. 反转链表 II 中等 同样先保存待改区间的前驱与后继，再把处理后的链段接回两端。
21. 合并两个有序链表 简单 原题按数值交错归并，本题整条第二链表替换第一链表的一段，不改变第二链内部顺序。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/71454417
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！