在Python中合并两个链表的指定区间

在数据结构中，链表是一种用于存储数据的重要数据结构。在Python中，也提供了很多实现链表的方式。本文将讨论如何在Python中合并两个链表的指定区间。

链表的定义

链表是由节点组成的数据结构，每个节点包含数据和指向下一个节点的指针。链表可以有多个节点，每个节点之间通过指针连接起来，形成一条链表。

在Python中，链表可以通过定义一个类来实现。下面是一个简单的链表类的定义：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

其中，ListNode是节点类的类名，val表示节点中存储的数据，next表示指向下一个节点的指针。

链表的操作

链表支持插入、删除、查找等基本操作。下面是链表类中的一些基本操作：

在链表中插入一个节点

def insert(self, node):
    node.next = self.next
    self.next = node

在链表中删除一个节点

def delete(self, node):
    prev_node = self
    current_node = self.next
    while current_node != None:
        if current_node == node:
            prev_node.next = current_node.next
            return
        prev_node = current_node
        current_node = current_node.next

查找链表中的某个节点

def search(self, val):
    current_node = self.next
    while current_node != None:
        if current_node.val == val:
            return current_node
        current_node = current_node.next
    return None

合并两个链表的指定区间

假设我们有两个链表l1和l2，我们要合并它们的区间[start1, end1]和[start2, end2]，合并后的链表为l3。

解法一：获得指定区间中的节点，然后插入到新链表中

我们可以先遍历l1，获得区间[start1, end1]中的节点，然后插入到新链表l3中。

接着遍历l2，获得区间[start2, end2]中的节点，然后插入到l3中。

这种方法的时间复杂度为O(n1+n2)，空间复杂度为O(n1+n2)。

下面是代码实现：

class Solution:
    def merge(self, l1: ListNode, start1: int, end1: int, l2: ListNode, start2: int, end2: int) -> ListNode:
        # 遍历l1，获得区间[start1, end1]中的节点，插入到l3中
        l3 = ListNode()
        current_node = l1.next
        index = 1
        while current_node != None and index < start1:
            current_node = current_node.next
            index += 1
        while current_node != None and index <= end1:
            l3.insert(ListNode(current_node.val))
            current_node = current_node.next
            index += 1

        # 遍历l2，获得区间[start2, end2]中的节点，插入到l3中
        current_node = l2.next
        index = 1
        while current_node != None and index < start2:
            current_node = current_node.next
            index += 1
        while current_node != None and index <= end2:
            l3.insert(ListNode(current_node.val))
            current_node = current_node.next
            index += 1

        return l3

解法二：使用双指针遍历链表

我们使用两个指针p1和p2，分别指向l1和l2的区间[start1, end1]和[start2, end2]的起点。比较p1和p2指向的节点，将较小的或相等的节点插入到新链表l3中，并向后移动指针，直到p1和p2都到达各自的区间末尾。如果l1和l2有一个链表遍历完了，那就把另一个链表剩下的节点都插入到l3中。

这种方法的时间复杂度为O(n1+n2)，空间复杂度为O(1)。

下面是代码实现：

class Solution:
    def merge(self, l1: ListNode, start1: int, end1: int, l2: ListNode, start2: int, end2: int) -> ListNode:
        # 定义p1和p2指向区间[start1, end1]和[start2, end2]的起点
        p1, p2 = l1.next, l2.next
        for i in range(1, start1):
            p1 = p1.next
        for j in range(1, start2):
            p2 = p2.next

        # 定义指向新链表l3的指针
        dummy_head = ListNode()
        curr_node = dummy_head

        # 合并两个链表的指定区间
        while p1 != None and p2 != None and end1 >= start1 and end2 >= start2:
            if p1.val <= p2.val:
                curr_node.next = ListNode(p1.val)
                p1 = p1.next
                start1 += 1
            else:
                curr_node.next = ListNode(p2.val)
                p2 = p2.next
                start2 += 1
            curr_node = curr_node.next

        # 把剩下的节点插入到新链表l3中
        while p1 != None and start1 <= end1:
            curr_node.next = ListNode(p1.val)
            p1 = p1.next
            start1 += 1
            curr_node = curr_node.next

        while p2 != None and start2 <= end2:
            curr_node.next = ListNode(p2.val)
            p2 = p2.next
            start2 += 1
            curr_node = curr_node.next

        return dummy_head.next