1669-合并两个链表

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

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

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

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2020/11/28/fig1.png)

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

示例 1：

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2020/11/28/merge_linked_list_ex1.png)

**输入：** 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：

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2020/11/28/merge_linked_list_ex2.png)

**输入：** 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 <= 104
• 1 <= a <= b < list1.length - 1
• 1 <= list2.length <= 104

方法一：模拟

思路与算法

题目要求将 list}_1 的第 a 到 b 个节点都删除，将其替换为 list}_2。因此，我们首先找到 list}_1 中第 a - 1 个节点 preA，以及第 b + 1 个节点 aftB。由于 1 \le a \le b \lt n - 1（其中 n 是 list}_1 的长度），所以 preA 和 aftB 是一定存在的。

然后我们让 preA 的 next 指向 list}_2 的头节点，再让 list}_2 的尾节点的 next 指向 aftB 即可。

代码

[sol1-Python3]

class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        preA = list1
        for _ in range(a - 1):
            preA = preA.next
        preB = preA
        for _ in range(b - a + 2):
            preB = preB.next
        preA.next = list2
        while list2.next:
            list2 = list2.next
        list2.next = preB
        return list1

[sol1-C++]

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* preB = preA;
        for (int i = 0; i < b - a + 2; i++) {
            preB = preB->next;
        }
        preA->next = list2;
        while (list2->next != nullptr) {
            list2 = list2->next;
        }
        list2->next = preB;
        return list1;
    }
};

[sol1-Java]

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 preB = preA;
        for (int i = 0; i < b - a + 2; i++) {
            preB = preB.next;
        }
        preA.next = list2;
        while (list2.next != null) {
            list2 = list2.next;
        }
        list2.next = preB;
        return list1;
    }
}

[sol1-C#]

public 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 preB = preA;
        for (int i = 0; i < b - a + 2; i++) {
            preB = preB.next;
        }
        preA.next = list2;
        while (list2.next != null) {
            list2 = list2.next;
        }
        list2.next = preB;
        return list1;
    }
}

[sol1-C]

struct ListNode* mergeInBetween(struct ListNode* list1, int a, int b, struct ListNode* list2) {
    struct ListNode* preA = list1;
    for (int i = 0; i < a - 1; i++) {
        preA = preA->next;
    }
    struct ListNode* preB = preA;
    for (int i = 0; i < b - a + 2; i++) {
        preB = preB->next;
    }
    preA->next = list2;
    while (list2->next != NULL) {
        list2 = list2->next;
    }
    list2->next = preB;
    return list1;
}

[sol1-JavaScript]

var mergeInBetween = function(list1, a, b, list2) {
    let preA = list1;
    for (let i = 0; i < a - 1; i++) {
        preA = preA.next;
    }
    let preB = preA;
    for (let i = 0; i < b - a + 2; i++) {
        preB = preB.next;
    }
    preA.next = list2;
    while (list2.next) {
        list2 = list2.next;
    }
    list2.next = preB;
    return list1;
};

[sol1-Golang]

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

复杂度分析

• 时间复杂度：O(n + m)，其中 n 是 list}_1 的长度，m 是 list}_2 的长度。
• 空间复杂度：O(1)。