Leetcode 92. Reverse Linked List II

Problem

Leetcode 92 - Reverse Linked List II

Example:

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

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

Approach

We can use a helper function called reverseList where it reverses linked list, but how do we know what the ‘head’ of reversing list is going to be?

We can find this out by shifting left pointer of linked list. Say in our exmaple head = [1,2,3,4,5] and left = 2 and right = 4

We can unlink the subset [2,3,4] then reverse the list first then re-link the using prev, after pointer which points at left-1 pointer and right+1 pointer.

Here is the Python code for the solution:

class Solution:
    def reverseList(self, head):
        prev, curr = None, head
        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp

        return prev

    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        leftNode, rightNode = head, head
        prev, after = dummy, dummy

        for _ in range(left-1):
            prev = prev.next
            leftNode = leftNode.next
        for _ in range(right-1):
            rightNode = rightNode.next
        
        after = rightNode.next
        rightNode.next = None
        reverse = self.reverseList(leftNode)

        prev.next = reverse
        leftNode.next = after

        return dummy.next
    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$