# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next



class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


#  方法一 迭代
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        dummyNode = ListNode(-1)
        dummyNode.next = head
        prev = dummyNode
        for i in range(left - 1):
            prev = prev.next
        curr = prev.next
        for i in range(right - left):
            next = curr.next
            curr.next = next.next
            next.next = prev.next
            prev.next = next
        return dummyNode.next


# 方法二 递归
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        def reverseN(head, n):
            if n == 1:
                global successor
                successor = head.next
                return head

            last = reverseN(head.next, n-1)
            head.next.next = head
            head.next = successor
            return last

        if left == 1:
            return reverseN(head, right)

        head.next = self.reverseBetween(head.next, left-1, right-1)
        return head