Medium
题目描述
给定两个链表：list1 和 list2，大小分别为 n 和 m。
删除 list1 中从第 a 个节点到第 b 个节点的所有节点，并将 list2 放在它们的位置。
下图中的蓝色边和节点表示结果：
构建结果链表并返回其头节点。
示例 1：
输入：list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[10,1,13,1000000,1000001,1000002,5]
解释：我们删除节点 3 和 4，并将整个 list2 放在它们的位置。上图中的蓝色边和节点表示结果。
示例 2：
输入：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
解题思路
这道题的核心思路是找到需要修改的连接点，然后重新连接链表。
解题步骤：
定位关键节点：我们需要找到 list1 中的第 (a-1) 个节点和第 (b+1) 个节点。第 (a-1) 个节点将成为连接 list2 头部的节点，第 (b+1) 个节点将成为连接 list2 尾部的节点。
遍历定位：使用一次遍历找到这两个关键节点。由于节点索引从 0 开始，我们需要遍历到第 (a-1) 个位置和第 (b+1) 个位置。
找到 list2 的尾节点：遍历 list2 找到其最后一个节点，这样才能正确连接到 list1 的后半部分。
重新连接：
- 将第 (a-1) 个节点的 next 指向 list2 的头节点
- 将 list2 的尾节点的 next 指向第 (b+1) 个节点
实现细节：
- 使用计数器遍历链表定位节点位置
- 注意索引是从 0 开始的，所以要删除的区间是 [a, b]
- 确保正确处理边界情况
这种方法只需要遍历链表几次，时间复杂度为 O(n+m)，空间复杂度为 O(1)。
代码实现
class Solution {
public:
ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
// 找到第(a-1)个节点
ListNode* nodeBeforeA = list1;
for (int i = 0; i < a - 1; i++) {
nodeBeforeA = nodeBeforeA->next;
}
// 找到第(b+1)个节点
ListNode* nodeAfterB = nodeBeforeA;
for (int i = a - 1; i <= b; i++) {
nodeAfterB = nodeAfterB->next;
}
// 找到list2的尾节点
ListNode* list2Tail = list2;
while (list2Tail->next != nullptr) {
list2Tail = list2Tail->next;
}
// 重新连接
nodeBeforeA->next = list2;
list2Tail->next = nodeAfterB;
return list1;
}
};
class Solution:
def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
# 找到第(a-1)个节点
node_before_a = list1
for i in range(a - 1):
node_before_a = node_before_a.next
# 找到第(b+1)个节点
node_after_b = node_before_a
for i in range(a - 1, b + 1):
node_after_b = node_after_b.next
# 找到list2的尾节点
list2_tail = list2
while list2_tail.next:
list2_tail = list2_tail.next
# 重新连接
node_before_a.next = list2
list2_tail.next = node_after_b
return list1
public class Solution {
public ListNode MergeInBetween(ListNode list1, int a, int b, ListNode list2) {
// 找到第(a-1)个节点
ListNode nodeBeforeA = list1;
for (int i = 0; i < a - 1; i++) {
nodeBeforeA = nodeBeforeA.next;
}
// 找到第(b+1)个节点
ListNode nodeAfterB = nodeBeforeA;
for (int i = a - 1; i <= b; i++) {
nodeAfterB = nodeAfterB.next;
}
// 找到list2的尾节点
ListNode list2Tail = list2;
while (list2Tail.next != null) {
list2Tail = list2Tail.next;
}
// 重新连接
nodeBeforeA.next = list2;
list2Tail.next = nodeAfterB;
return list1;
}
}
var mergeInBetween = function(list1, a, b, list2) {
// 找到第(a-1)个节点
let nodeBeforeA = list1;
for (let i = 0; i < a - 1; i++) {
nodeBeforeA = nodeBeforeA.next;
}
// 找到第(b+1)个节点
let nodeAfterB = nodeBeforeA;
for (let i = a - 1; i <= b; i++) {
nodeAfterB = nodeAfterB.next;
}
// 找到list2的尾节点
let list2Tail = list2;
while (list2Tail.next !== null) {
list2Tail = list2Tail.next;
}
// 重新连接
nodeBeforeA.next = list2;
list2Tail.next = nodeAfterB;
return list1;
};
复杂度分析
| 复杂度 | 大小 |
|---|---|
| 时间复杂度 | O(n + m) |
| 空间复杂度 | O(1) |
其中 n 是 list1 的长度，m 是 list2 的长度。时间复杂度主要来自于遍历两个链表找到关键节点，空间复杂度为常数级别，只使用了几个指针变量。