medium Reverse Linked List II

Problem Statement

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

Examples

Example 1:

• Input: [7, 8, 9, 10, 11], left = 2, right = 4
• Expected Output: [7, 10, 9, 8, 11]
• Justification: The nodes from position 2 to 4 (8, 9, 10) are reversed to become 10, 9, 8.

Example 2:

• Input: [1, 2, 3, 4, 5, 6], left = 2, right = 5
• Expected Output: [1, 5, 4, 3, 2, 6]
• Justification: The nodes from position 2 to 5 (2, 3, 4, 5) are reversed to become 5, 4, 3, 2.

Example 3:

• Input: [5, 6, 7, 8, 9], left = 1, right = 3
• Expected Output: [7, 6, 5, 8, 9]
• Justification: The nodes from position 1 to 3 (5, 6, 7) are reversed to become 7, 6, 5.

Constraints:

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

Solution

To solve this problem, we will use a two-pointer technique along with a dummy node to simplify edge cases. The approach involves moving two pointers to the positions just before and at the start of the sublist that needs to be reversed. We'll then reverse the sublist in-place by adjusting the pointers.

This approach is effective because it allows us to reverse the specific portion of the list without needing extra space for another list, keeping the space complexity low. By adjusting pointers directly, we ensure that the solution is efficient and runs in linear time relative to the length of the list.

Step-by-Step Algorithm

1. Initialize a dummy node:

   • Create a dummy node with value 0 and set its next pointer to the head of the list. This helps to handle edge cases smoothly.
   • Initialize a pointer prev to point to the dummy node.

2. Move prev to the node just before the start of the sublist to be reversed:

   • Iterate left - 1 times to move prev to the node right before the position left.

3. Initialize pointers for reversing the sublist:

   • Set a pointer start to prev.next, which points to the first node in the sublist to be reversed.
   • Set a pointer then to start.next, which points to the node after start.

4. Reverse the sublist from position left to right:

   • Perform the reversal right - left times:
     • Set start.next to then.next.
     • Set then.next to prev.next.
     • Set prev.next to then.
     • Move then to start.next.

5. Return the new head of the list:

   • Return dummy.next, which points to the new head of the list after reversal.

Algorithm Walkthrough

Let's walk through the example input [1, 2, 3, 4, 5, 6], left = 2, right = 5 step by step.

1. Initialize a dummy node:

   • dummy -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
   • prev points to dummy.

2. Move prev to the node just before the start of the sublist:

   • Iterate left - 1 = 2 - 1 = 1 times.
   • After 1 iteration, prev points to the node with value 1.
   • Now, prev -> 1 -> 2 -> 3 -> 4 -> 5 -> 6

3. Initialize pointers for reversing the sublist:

   • start -> 2 -> 3 -> 4 -> 5 -> 6
   • then -> 3 -> 4 -> 5 -> 6

4. Reverse the sublist from position left to right:

   • Perform the reversal right - left = 5 - 2 = 3 times.

   • First iteration:

     • start.next -> 4 -> 5 -> 6
     • then.next -> 2 -> 4 -> 5 -> 6
     • prev.next -> 3 -> 2 -> 4 -> 5 -> 6
     • Move then to start.next -> 4 -> 5 -> 6
     • List now looks like: 0 -> 1 -> 3 -> 2 -> 4 -> 5 -> 6

   • Second iteration:

     • start.next -> 5 -> 6
     • then.next -> 3 -> 2 -> 5 -> 6
     • prev.next -> 4 -> 3 -> 2 -> 5 -> 6
     • Move then to start.next -> 5 -> 6
     • List now looks like: 0 -> 1 -> 4 -> 3 -> 2 -> 5 -> 6

   • Third iteration:

     • start.next -> 6
     • then.next -> 4 -> 3 -> 6
     • prev.next -> 5 -> 4 -> 3 -> 2 -> 6
     • Move then to start.next -> 6
     • List now looks like: 0 -> 1 -> 5 -> 4 -> 3 -> 2 -> 6

5. Return the new head of the list:

   • Return dummy.next, which is the node with value 1.

The final modified list after reversal is [1, 5, 4, 3, 2, 6].

Code

// class ListNode {
//     int val;
//     ListNode next;
//     ListNode(int x) { val = x; }
// }

class Solution {

  public ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null) return null;

    // Create a dummy node to simplify edge cases
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;

    // Move prev to the node just before the start of the sublist to be reversed
    for (int i = 1; i < left; i++) {
      prev = prev.next;
    }

    // The current node at the start of the sublist to be reversed
    ListNode start = prev.next;
    ListNode then = start.next;

    // Reverse the sublist from left to right
    for (int i = 0; i < right - left; i++) {
      start.next = then.next;
      then.next = prev.next;
      prev.next = then;
      then = start.next;
    }

    return dummy.next;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    ListNode head1 = new ListNode(7);
    head1.next = new ListNode(8);
    head1.next.next = new ListNode(9);
    head1.next.next.next = new ListNode(10);
    head1.next.next.next.next = new ListNode(11);
    ListNode result1 = solution.reverseBetween(head1, 2, 4);
    printList(result1); // Expected output: [7, 10, 9, 8, 11]

    // Example 2
    ListNode head2 = new ListNode(1);
    head2.next = new ListNode(2);
    head2.next.next = new ListNode(3);
    head2.next.next.next = new ListNode(4);
    head2.next.next.next.next = new ListNode(5);
    head2.next.next.next.next.next = new ListNode(6);
    ListNode result2 = solution.reverseBetween(head2, 2, 5);
    printList(result2); // Expected output: [1, 5, 4, 3, 2, 6]

    // Example 3
    ListNode head3 = new ListNode(5);
    head3.next = new ListNode(6);
    head3.next.next = new ListNode(7);
    head3.next.next.next = new ListNode(8);
    head3.next.next.next.next = new ListNode(9);
    ListNode result3 = solution.reverseBetween(head3, 1, 3);
    printList(result3); // Expected output: [7, 6, 5, 8, 9]
  }

  // Helper method to print the list
  public static void printList(ListNode head) {
    while (head != null) {
      System.out.print(head.val + " ");
      head = head.next;
    }
    System.out.println();
  }
}

Complexity Analysis

Time Complexity:

We traverse the linked list a few times: once to reach the position before the sublist to be reversed, and then to reverse the sublist. This results in complexity, where n is the number of nodes in the list.

Space Complexity:

The algorithm uses a constant amount of extra space regardless of the input size. We only use a few pointers for reversing the sublist.