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

# 解题思路：
# 1、找到要反转的节点并且将记录各个边界节点的位置（根据m和n来确定）
# 2、断开原本的边界连接 
# 3、反转指定区间的链表（把他视为一个新的链表） 
# 4、拼接回原本的链表

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def reverseBetween(self, head, m, n):
        # 第m到第n个之间反转
        p0 = ListNode(999)  # 考虑到的特殊情况，如果区间是1的话会出现问题。
        p0.next = head  # 将p0作为头节点
        time = 0  # 记录找到第几个
        # 思路：找到边界和临界节点
        front = None  # m的前一个节点
        first = None  # m处的节点
        tail = None  # n处的节点
        butt = None  # n的后一个节点
        # 首先确定各个节点的位置，将指针指向对应的节点；可以通过m和n来确定
        x = p0
        while x != None:
            if time == m - 1:
                front = x
            if time == m:
                first = x
            if time == n:
                tail = x
            if time == n + 1:
                butt = x
                break  # 找到最后的节点可以停止
            time += 1
            x = x.next
        # 找到之后，断开各个节点，单独拿出来反转后拼接
        front.next = None
        tail.next = None
        pre = None
        cur = first
        next = cur
        newtail = None  # 为了拼接还需要找到尾节点
        while cur:

            next = next.next
            cur.next = pre
            pre = cur
            if cur.next == None:
                newtail = cur
            cur = next

        # 此时反转完成后，pre作为反转的头节点，尾节点是newtail
        # 拼接：
        front.next = pre
        newtail.next = butt
        return p0.next