合并两个链表

难度: 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]
解释：我们删除 list1 中下标为 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⁴
1 <= a <= b < list1.length - 1
1 <= list2.length <= 10⁴

Submission

运行时间: 360 ms

内存: 20.9 MB

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        dummy = ListNode(next=list1)
        p2 = list1
        for _ in range(b+1):
            p2 = p2.next
        p1 = dummy
        for _ in range(a):
            p1 = p1.next
        p1.next = list2
        p3 = list2
        while p3.next:
            p3 = p3.next
        p3.next = p2
        return dummy.next

Explain

这个题解的思路是首先使用一个虚拟头结点(dummy node)指向list1的头部，以简化边界条件处理。接着，使用两个指针p1和p2来定位需要删除的链表部分的前驱和后继节点。p1指向位置a前的节点，而p2则指向位置b的下一个节点。然后，将list2的头部接到p1的后面，即p1.next = list2。之后，遍历到list2的尾部，将其与p2连接，完成链表的合并。这样不仅保持了list1中未删除部分的原有顺序，还将list2完整插入到了指定位置。

时间复杂度: O(n + m)

空间复杂度: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        dummy = ListNode(next=list1)  # 创建虚拟头结点，简化边界处理
        p2 = list1
        for _ in range(b+1):
            p2 = p2.next  # 移动p2到b位置的下一个节点
        p1 = dummy
        for _ in range(a):
            p1 = p1.next  # 移动p1到a位置前一个节点
        p1.next = list2  # 将list2接在p1后面
        p3 = list2
        while p3.next:
            p3 = p3.next  # 找到list2的末尾
        p3.next = p2  # 将list2末尾与p2连接
        return dummy.next  # 返回合并后的链表头部

Explore

虚拟头结点（dummy node）主要用于简化链表操作中的边界条件处理。通过在原始链表list1的前面添加一个虚拟头结点，可以确保即使需要修改的是链表的首个元素，也总有一个节点位于需要修改节点的前面。这样，无论操作涉及到链表的开头、中间还是结尾，处理逻辑都能保持一致，避免了处理头节点特殊情况的复杂性。例如，当需要删除或添加头节点时，通过使用虚拟头结点，可以避免单独判断是否为头节点的情况，使代码更加简洁和健壮。

如果list1的长度n小于b，题解中的方法将会出现问题，因为在尝试访问b位置的下一个节点时（p2 = p2.next），将会因为p2已经是null而试图访问null的next属性，从而引发运行时错误。在实际应用中，应该先检查链表长度是否满足条件，即a和b的值是否在合理的范围内，这样可以避免运行时错误，并保证算法的健壮性。

当a为0时，意味着需要从list1的首节点开始删除部分链表。由于使用了虚拟头结点，p1将初始化为dummy，而dummy.next指向list1的头节点。因此，当for循环结束时（for _ in range(a)），p1仍然指向虚拟头结点，这样p1.next直接指向list2即可。这意味着原始链表的开始部分被替换为list2，而dummy节点确保了即使从首节点开始删除，算法逻辑也不需要任何特殊处理。

如果list2为空，即list2为null或其头节点为null，在连接过程中p1.next = list2将导致原本由p1指向的位置直接连接到p2，相当于直接删除了原链表中a到b位置的所有元素。因此，如果list2为空，实际上没有插入任何新元素，只是删除了list1中指定的部分。这种情况下，算法仍然有效，可以视为一种特殊情况的处理，即删除而非插入操作。