LC 1669. 合并两个链表

题目描述

这是 LeetCode 上的 1669. 合并两个链表 ，难度为 中等。

给你两个链表 list1 和 list2，它们包含的元素分别为 n 个和 m 个。

请你将 list1 中下标从 a 到 b 的全部节点都删除，并将 list2 接在被删除节点的位置。

下图中蓝色边和节点展示了操作后的结果：

请你返回结果链表的头指针。

示例 1：

1
2
3
4
5
输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]

输出：[0,1,2,1000000,1000001,1000002,5]

解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。

示例 2：

1
2
3
4
5
输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]

输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]

解释：上图中蓝色的边和节点为答案链表。

提示：

  • $3 <= list1.length <= 10^4$
  • $1 <= a <= b < list1.length - 1$
  • $1 <= list2.length <= 10^4$

模拟

根据题意进行模拟即可。

使用两个变量 A 和 B 分别指向 list1 中两个断联的位置，分别将 A 指向 list2 的开头，将 list2 的 next 指针指向 B。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode ans = list1;
        ListNode A = null, B = null;
        while (--a > 0 && --b > 0) list1 = list1.next;
        A = list1;
        while (b-- > 0) list1 = list1.next;
        B = list1;
        A.next = list2;
        while (list2.next != null) list2 = list2.next;
        list2.next = B.next;
        return ans;
    }
}

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
function mergeInBetween(list1: ListNode | null, a: number, b: number, list2: ListNode | null): ListNode | null {
    const ans = list1
    let A = null, B = null
    while (--a > 0 && --b > 0) list1 = list1.next
    A = list1
    while (b-- > 0) list1 = list1.next
    B = list1
    A.next = list2
    while (list2.next != null) list2 = list2.next
    list2.next = B.next
    return ans
}

  • 时间复杂度：$O(n + m)$
  • 空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1699 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。