92. Reverse Linked List 2

Problem Statement in English

You’re 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.

Approach

Since we know the left and right positions we know exactly how much we need to iterate.

So we move our prev pointer to the node just before the left position. Then we reverse the sublist from left to right using a standard linked list reversal technique¹.

Finally, we reconnect the reversed sublist back to the original list using the prev pointer and the tail pointer.

¹The standard linked list technique involves storing the current node, the previous node, and the next node. We then make the current node point to the previous node, make the previous node the current node, and make the current node the next node.

And we’re done!

Solution in Python

class Solution:
    def reverseBetween(self, head: ListNode | None, left: int, right: int) -> ListNode | None:
        if not head or left == right:
            return head

        dummy = ListNode(0, head)
        prev = dummy

        for _ in range(left - 1):
            prev = prev.next

        tail = prev.next
        curr = tail
        prev_node = None

        for _ in range(right - left + 1):
            next_node = curr.next
            curr.next = prev_node
            prev_node = curr
            curr = next_node

        prev.next = prev_node
        tail.next = curr

        return dummy.next

Complexity

• Time: $O(n)$
  Since we traverse the linked list once to reach the left position and then reverse the sublist from left to right, the overall time complexity is linear with respect to the number of nodes in the linked list.

• Space: $O(1)$
  Since we are reversing the linked list in place and not using any additional data structures that scale with input size, the space complexity is constant.

Mistakes I Made

My approach was overcomplicated.

And we are done.