题解 | #链表内指定区间反转#

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param m int整型 
# @param n int整型 
# @return ListNode类
#
class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        # 保留原始头节点的初始指针
        flag = ListNode(-1)
        flag.next = head
        # 初始化前一个节点和当前节点。
        previous = flag
        current = head
        idx = 1

        # 链表被拆分为了3个部分：[1, m), [m, n], [n+1, end]，并分别进行处理。

        # 处理[1, m)部分。
        while idx < m:
            # 第m个节点之前的节点，逐步后移就行，只需要记录到第m个节点的前一个节点的指针。
            previous = current
            current = current.next
            idx += 1


        # 记录第m个节点的前一个节点的指针，它将用于链接[1, m)和[m, n]这两部分。
        previous_m = previous
        # 记录第m个节点的指针。第m个节点是逆序链表的最后一个节点，它将用于链接[m, n]和[n+1, end]这两部分
        current_m = current

        # 处理[m, n]部分。对m到n之间的链表逆序。
        while idx <= n:
            # 保留下一个节点的指针，防止链表断开。
            next_node_pointer = current.next
            # 让当前节点的下一个变成它的上一个节点。
            # 这一步会使逆序链表和它后面的链表断开，所以之前要记录第m个节点的指针，
            # 之前的第m个节点是逆序链表的最后一个节点，
            # 最后要让第m个节点的next指针指向第n个节点之后的链表，把链表链接完整。
            current.next = previous
            # 当前节点将作为下一次循环的上一个节点
            previous = current
            # 让指针指向下一个节点。
            current = next_node_pointer
            idx += 1

        # 链表被拆分为了3个部分：[1, m), [m, n], [n+1, end]。
        # 其中[m, n]部分被逆序。
        previous_m.next = previous  # 拼接[1, m)和 [m, n]这两部分为[1, n]。
        current_m.next = current  # 拼接[1, n)和[n+1, end]为[1, end]。

        return flag.next