Reverse Linked List II

• Create a dummy node and set dummy.next = head. This simplifies handling the edge case where left = 1.
• Create a pointer pre_left and initialize it to dummy.
• Move pre_left forward left - 1 times. After the loop, pre_left will be at the node just before the sublist to be reversed.
• Initialize current = pre_left.next. This current pointer marks the start of the sublist to be reversed and will eventually become its tail.
• Loop right - left times. This is the core of the reversal:
  • a. Let node_to_move = current.next. This is the node we will move to the front of the reversed section.
  • b. Detach node_to_move from its current position by setting current.next = node_to_move.next.
  • c. Prepend node_to_move to the reversed part by setting node_to_move.next = pre_left.next.
  • d. Update the link from the preceding part of the list by setting pre_left.next = node_to_move.
• After the loop completes, the sublist from left to right is reversed and correctly linked with the rest of the list.
• Return dummy.next, which is the head of the modified list.

This iterative approach is the standard and most efficient solution. It directly manipulates the node pointers in-place to achieve the reversal.

• We use a dummy node to simplify edge cases, such as when the reversal starts at the head of the list (left = 1). The dummy node points to the original head.
• First, we iterate left - 1 times to find the node just before the sublist to be reversed. Let's call this pre_left.
• We then identify the start of our sublist, current = pre_left.next. This current node will act as a pivot and will become the tail of the reversed sublist after all operations.
• We then loop right - left times. In each iteration, we take the node immediately following current (let's call it node_to_move) and move it to become the new first node of the sublist (i.e., right after pre_left).

Let's trace [1,2,3,4,5], left=2, right=4:

• Initial: dummy -> 1 -> 2 -> 3 -> 4 -> 5. pre_left is at 1, current is at 2.
• Iteration 1 (move 3): node_to_move is 3. The list becomes dummy -> 1 -> 3 -> 2 -> 4 -> 5.
• Iteration 2 (move 4): node_to_move is 4. The list becomes dummy -> 1 -> 4 -> 3 -> 2 -> 5.

After the loop, the sublist is reversed, and all connections are correctly updated. We return dummy.next.

1class Solution {2    public ListNode reverseBetween(ListNode head, int left, int right) {3        if (head == null || left == right) {4            return head;5        }6 7        ListNode dummy = new ListNode(0);8        dummy.next = head;9        // 1. Reach node at position `left - 1`10        ListNode pre_left = dummy;11        for (int i = 0; i < left - 1; i++) {12            pre_left = pre_left.next;13        }14 15        // 2. `current` points to the node at position `left`16        ListNode current = pre_left.next;17 18        // 3. Reverse the sublist19        for (int i = 0; i < right - left; i++) {20            ListNode node_to_move = current.next;21            current.next = node_to_move.next;22            node_to_move.next = pre_left.next;23            pre_left.next = node_to_move;24        }25 26        return dummy.next;27    }28}

• If head is null or left == right, there's nothing to reverse, so return head.
• Create an ArrayList<Integer> to store the values of the nodes.
• Traverse the linked list from the head with a pointer, current, and add the value of each node (current.val) to the ArrayList.
• After the list is fully traversed, the ArrayList contains all node values in order.
• Reverse the sub-array within the ArrayList from index left - 1 to right - 1. This can be done with a two-pointer approach, swapping elements from both ends of the sub-array until the pointers meet.
• Reset the current pointer back to the head of the linked list.
• Iterate through the ArrayList from the beginning, and for each value, update the corresponding node in the linked list: current.val = arraylist.get(i). Move current to the next node.
• Return the original head of the list, which now contains the modified values.

This is a straightforward but less efficient approach. The core idea is to avoid complex pointer manipulation by offloading the reversal logic to a more convenient data structure, an array.

• First, we traverse the entire linked list and store the value of each node in a dynamic array (like ArrayList in Java).
• Once all values are in the array, we reverse the portion of the array from index left - 1 to right - 1. This can be done using a standard two-pointer swapping technique.
• Finally, we traverse the linked list a second time from the head. In this traversal, we update the value of each node with the corresponding value from our modified array.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public ListNode reverseBetween(ListNode head, int left, int right) {7        if (head == null || left == right) {8            return head;9        }10 11        // 1. Copy list values to an ArrayList12        List<Integer> values = new ArrayList<>();13        ListNode current = head;14        while (current != null) {15            values.add(current.val);16            current = current.next;17        }18 19        // 2. Reverse the sublist of values20        int l = left - 1;21        int r = right - 1;22        while (l < r) {23            int temp = values.get(l);24            values.set(l, values.get(r));25            values.set(r, temp);26            l++;27            r--;28        }29 30        // 3. Update the linked list with the new values31        current = head;32        for (int val : values) {33            current.val = val;34            current = current.next;35        }36 37        return head;38    }39}

• The main function reverseBetween(head, left, right) serves as the entry point.
• Base Case: If left == 1, it means the reversal starts from the current head. We then call a helper function, reverseN(head, right), which is responsible for reversing the first right nodes of a list.
• Recursive Step: If left > 1, the current head is not part of the sublist to be reversed. We keep it in place and make a recursive call on the rest of the list: head.next = reverseBetween(head.next, left - 1, right - 1). This effectively moves our 'window' of reversal one step down the list.
• The helper function reverseN(head, n) reverses the first n nodes:
  • It uses a class-level variable successor to keep track of the node that comes after the sublist being reversed.
  • Base Case: If n == 1, we've reached the end of the sublist. We store head.next in successor and return head.
  • Recursive Step: It calls reverseN(head.next, n - 1). When this call returns, it provides the new head of the reversed tail (last). We then rewire the pointers: head.next.next points back to head, and head.next points to the saved successor.
  • It returns last, which propagates the new head of the reversed section up the call stack.

This approach leverages the call stack to manage the state of the reversal. It's an elegant way to think about the problem by breaking it down into smaller, self-similar subproblems.

The solution is broken down into two parts:

1. A main recursive function reverseBetween(head, left, right) that navigates to the start of the sublist to be reversed.
2. A helper recursive function reverseN(head, n) that reverses the first n nodes of a given list.

The reverseBetween function decrements left and right and calls itself on head.next until left becomes 1. This means we have reached the starting node for reversal. When left is 1, it calls reverseN(head, right) to perform the actual reversal of right nodes.

The reverseN function works by recursively reversing n-1 nodes from head.next. On the way back up the call stack, it reverses the pointers. A key detail is to save the (n+1)-th node (the successor) before the recursion, so the reversed sublist can be correctly linked back to the rest of the list.

1class Solution {2    private ListNode successor = null;3 4    // Reverses the first n nodes of the list starting at head5    private ListNode reverseN(ListNode head, int n) {6        if (n == 1) {7            // Base case: reached the end of the sublist to reverse8            successor = head.next; // Save the node after the sublist9            return head;10        }11        // Recurse on the rest of the list12        ListNode last = reverseN(head.next, n - 1);13        head.next.next = head;14        // Connect the reversed part to the successor15        head.next = successor;16        return last;17    }18 19    public ListNode reverseBetween(ListNode head, int left, int right) {20        if (left == 1) {21            // If reversal starts from the head, just reverse the first 'right' nodes22            return reverseN(head, right);23        }24        // Recurse until we reach the starting point of reversal25        // The subproblem is to reverse the list starting from head.next26        head.next = reverseBetween(head.next, left - 1, right - 1);27        return head;28    }29}