反转链表 II（LeetCode）

题目

给你单链表的头指针 $head$ 和两个整数 $left$ 和 $right$ ，其中 $left <=right$ 。请你反转从位置 $left$ 到位置 $right$ 的链表节点，返回 反转后的链表 。

解题

class ListNode:def __init__(self, value=0, next=None):self.value = valueself.next = nextdef reverseBetween(head: ListNode, left: int, right: int) -> ListNode:if left == 1:# 从头开始反转前 right 个节点return reverseN(head, right)# head 的 next 不变，但 next 部分从 left - 1 开始反转到 right - 1head.next = reverseBetween(head.next, left - 1, right - 1)return head# 辅助变量，记录第 n+1 个节点,以便在反转完成后重新连接链表。
successor = Nonedef reverseN(head: ListNode, n: int) -> ListNode:"""反转以 head 为起点的 n 个节点，返回新的头结点"""if n == 1:# 记录第 n+1 个节点global successorsuccessor = head.nextreturn head# 递归反转前 n-1 个节点last = reverseN(head.next, n - 1)head.next.next = head# 让反转之后的 head 节点和后面的节点连起来head.next = successorreturn last# 创建链表的辅助函数
def create_linked_list(elements):if not elements:return Nonereturn ListNode(elements[0], create_linked_list(elements[1:]))# 辅助函数：打印链表
def print_linked_list(head: ListNode):current = headwhile current:print(current.value, end=" -> " if current.next else "\n")current = current.nextif __name__ == '__main__':# 使用 create_linked_list 函数创建链表elements = [1, 2, 3, 4, 5]head = create_linked_list(elements)print("原始的链表:")print_linked_list(head)# 反转从位置 2 到位置 4 的链表部分left, right = 2, 4new_head = reverseBetween(head, left, right)# 打印反转后的链表print("反转一部分后的链表:")print_linked_list(new_head)