92-reverse-linked-list-ii

Try it on leetcode

Description

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

 

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

 

Follow up: Could you do it in one pass?

Solution(Python)

# 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: Optional[ListNode], left: int, right: int
    ) -> Optional[ListNode]:
        return self.recursion(head, left, right)

    # Time Complexity: O(N)
    # Space Complexity: O(N)
    def recursion(self, head: Optional[ListNode], m: int, n: int) -> Optional[ListNode]:
        if m == n:
            return head

        if m > 1:
            newHead = head
            newHead.next = self.recursion(head.next, m - 1, n - 1)
            return newHead
        else:
            next_ = head.next
            newHead = self.recursion(next_, 1, n - 1)
            nextnext_ = next_.next
            next_.next = head
            head.next = nextnext_
            return newHead