92. Reverse Linked List II

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # time O(N) space O(N)
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode: 
        self.successor = None
        def reverseN(head,n):
        # base case(termination condition): when n == 1, recursion has reached to nth node,return new head  
            if n == 1 :
                self.successor = head.next
                return head
            last = reverseN(head.next,n-1)
            head.next.next = head
            head.next = self.successor
            return last 
        # base case: start ptr is first node, so it's like reverse first n nodes in the linked list
        if m == 1 : 
            return reverseN(head,n)
        # think as [head] => reverse_recursion([head.next,....])
        head.next = self.reverseBetween(head.next,m-1,n-1)
        return head