BM2 链表内指定区间反转

题目描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转。
其中0 < m <= n <= size
size <= 1000

示例：
{1,2,3,4,5},2,4 -> {1,4,3,2,5}
{5},1,1 -> {5}

链接：https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&tqId=654&ru=%2Fpractice%2F75e878df47f24fdc9dc3e400ec6058ca&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj

解题思路

复习一下普通的头插法反转链表

头插法：
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None:
            return None
        pre_node = head
        node = pre_node.next
        pre_node.next = None
        while node is not None:
            next_node = node.next
            node.next = pre_node
            pre_node = node
            node = next_node
        return pre_node

要在指定区间内反转，实际上就是指定一个反转开始的起点start和终点end，反转区间内的所有节点即可。有以下几点需要注意：
1. 需要指定pre_start和next_end，在遍历开始前，start.next = end.next；在遍历完成后，pre_start.next = pre
2. 由于不确定m是否为1（如果是1的话那就是变为从头反转），可以在算法最开始设定一个res = ListNode(-1); res.next = head，算法结束时返回res即可。

解题代码

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int):
        res = ListNode(-1)
        res.next = head
        i = 1
        pre_start, start, end, next_end = res, head, head, head
        node = head
        while i <= n:
            if i == m - 1 and m != 1:
                pre_start = node
            if i == m:
                start = node
            if i == n:
                end = node
                next_end = node.next
            i += 1
            node = node.next
        node = start.next
        pre = start
        start.next = end.next
        while node != next_end:
            next_node = node.next
            node.next = pre
            pre = node
            node = next_node
        pre_start.next = pre
        return res.next