【leetcode】92. 反转链表 II（python）

思路详见注释

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverse(self, head):  
        pre = head
        cur = head.next
        pre.next = None
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        if not head or not head.next:
            return head
        dummy = ListNode(0,head)
        p = dummy

        for _ in range(left):
            pre = p    # pre 记录left的前驱节点
            p = p.next

        for _ in range(right - left):
            p = p.next

        nxt = p.next   # nxt 记录right的后继节点
        p.next = None  # 让right的的后继指向None, 截取出从left到right位置的节点

        pre.next = self.reverse(pre.next)  # 反转指定位置的链表

        while pre.next:  # 把反转后的从left到right的节点再接回去
            pre = pre.next
        pre.next = nxt
        return dummy.next