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}