Q1669-合并两个链表-中等-链表

1669. 合并两个链表

Question

给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。请你将 list1 中第 a 个节点到第 b 个节点删除，并将list2 接在被删除节点的位置。请你返回结果链表的头指针。

Example 1:

输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002] 输出：[0,1,2,1000000,1000001,1000002,5] 解释：我们删除 list1 中第三和第四个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。

Example 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

Approach 1: 链表合并

本题目思路很明确，主要需要注意以下几点：

合并过程中只用考虑指针，地址中的值不用转换。
链表不像数组，赋值只管头尾指针，不用每个位置都重新赋值
链表的遍历（计算长度），没有什么好方法

import math
from enum import Enum
import bisect
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


def stringToListNode(input):
    # Now convert that list into linked list
    dummyRoot = ListNode(0)
    ptr = dummyRoot
    for number in input:
        ptr.next = ListNode(number)
        ptr = ptr.next
    ptr = dummyRoot.next
    return ptr

def listNodeToString(node):
    if not node:
        return "[]"
    result = ""
    while node:
        result += str(node.val) + ", "
        node = node.next
    return "[" + result[:-2] + "]" # 最后一个逗号不输出


class Solution:
    def mergeInBetween(self, list1, a: int, b: int, list2):
        res = list1 # 存放答案头指针，在list1基础上合并
        num = 0 # 计数器
        while list1:
            # 找到 list1 的 a 处指针放入 start1
            if num == a-1:
                start1 = list1
            # 找到 list1 的 b 处指针放入 end1
            if num == b+1:
                end1 = list1
                break # 之后的长度不用管了
            list1 = list1.next
            num += 1
        # 找到 list2 的 尾部指针放入 end2
        start1.next = list2
        while list2.next:
            list2 = list2.next
        list2.next = end1
        return res


def main():
    list1 = stringToListNode([0,1,2,3,4,5])
    list2 = stringToListNode([1000000,1000001,1000002])
    a = 3
    b = 4
    solution=Solution().mergeInBetween(list1,a,b,list2)
    print(solution)


if __name__ == "__main__":
    main()

复杂度分析

时间复杂度：O(n)。其中n为 $链表长度链表长度$ 。
空间复杂度：O(1)。解决问题需要常数大小的辅助空间。