[LeetCode] 92. Reverse Linked List II

Problem : https://leetcode.com/problems/reverse-linked-list-ii/

Not really difficult. Be careful that the index starts from 1.  And it requires to reverse the list in range [m ~ n].

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        dummy = ListNode()
        p = dummy
              
        def helper(i, node):
            if not node:
                return node
            
            nonlocal p
            
            if i < m:
                # append current node keep list order
                p.next = node
                p = p.next
                return helper(i+1, node.next)
            elif i > n:
                # return rest of the list
                return node
            else:
                # reverse order with postorder traversal
                tail = helper(i+1,node.next)
                p.next = node
                p = p.next
                
                return tail
        
        # append rest of the list
        p.next = helper(1, head)
        
        return dummy.next

An iterative solution:

# Definition for singly-linked list.
# 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:
        dummy1 = ListNode() # the prefix list in original order
        dummy2 = ListNode() # reversed list
        
        p1 = dummy1
        p2 = dummy2
        p3 = None    # end of the reversed list
         
        while right >= 0:
            left -= 1
            right -= 1
            
            if left > 0:
                p1.next = head
                p1 = p1.next
                head = head.next
                continue
                
            if left <= 0 and right >= 0:
                if left == 0:
                    p3 = head
                    
                tmp = head
                head = head.next
                
                tmp.next = p2.next
                p2.next = tmp
                continue
            
        p1.next = p2.next
        p3.next = head
        
        return dummy1.next