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:

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

Example 2:

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

Constraints:

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

Solution

This again list manipulations problem. In this case, we are not required to reverse the full list but only a part of the list. So, we have to first find out the left position where we want to start reversal. Once we have found this node, we can start moving the pointer for next nodes in the reverse direction until we have reached the right node where we want to stop. For this, we can use the right as a counter.

After we have reversed the sublist, we have to connect the previous to original left with the right node and similarly, the left node needs to be connected to the next of right node. This requires us storing the prevToLeft and leftNode for later use.

 1class Solution {
 2    public ListNode reverseBetween(ListNode head, int left, int right) {
 3        if (head == null || head.next == null) {
 4            return head;
 5        }
 6        // Find previous node to left because this allows us to connect the reversed list to the rest of the list
 7        // Also find the leftNode using current
 8        ListNode current = head, prevToLeft = null;
 9        while (left > 1) {
10                prevToLeft = current;
11                current = current.next;
12                left--;
13                right--;
14        }
15        // Store previous node to left in prevToLeft as we will need it at the end to connect the reversed list to the rest of the list
16        // Also save leftNode as we will need it to connect to next element at the end.
17        ListNode prev = prevToLeft, leftNode = current, next = null;
18
19        // Reverse the list from left to right
20        while (right > 0) {
21            next = current.next;
22            current.next = prev;
23            prev = current;
24            current = next;
25            right--;
26        }
27        // At this point, prev points to the head of the reversed list
28        // current points to the next element after the reversed list
29
30        if (prevToLeft != null) // if left is not the first element
31            prevToLeft.next = prev;
32        else // if left is the first element
33            head = prev;
34
35        leftNode.next = current;
36
37        return head;
38    }
39}
  • Time Complexity: O(n)
  • Space Complexity: O(1)