链表内指定区间反转

问题简述

给定链表 head，把 m 到 n 区间内的节点反转

链表内指定区间反转_牛客题霸_牛客网

思路：模拟

Python

# 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
        
        # 增加一个伪头结点，主要针对完全反转的情况
        dummy = ListNode(0)
        dummy.next = head
        
        cnt = n - m
        pre, cur = dummy, head
        while m - 1:  # 因为要保存开始反转之前的一个节点，所以少移动一次
            m -= 1
            pre = cur
            cur = cur.next
        
        beg, end = pre, cur
        pre, cur = cur, cur.next  # 把少移动的一次补回来
        
        # 开始反转，反转 cnt 次
        while cnt:
            cnt -= 1
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        
        # 重新拼接（可以画图理解为什么是这两个位置拼接）
        beg.next = pre
        end.next = cur
        
        return dummy.next