Reverse Linked List II

This is the most optimal approach, solving the problem in a single pass with constant extra space. It involves careful pointer manipulation to reverse the sublist directly within the original list.

• 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.

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

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 1. Reach node at position `left - 1`
        ListNode pre_left = dummy;
        for (int i = 0; i < left - 1; i++) {
            pre_left = pre_left.next;
        }

        // 2. `current` points to the node at position `left`
        ListNode current = pre_left.next;

        // 3. Reverse the sublist
        for (int i = 0; i < right - left; i++) {
            ListNode node_to_move = current.next;
            current.next = node_to_move.next;
            node_to_move.next = pre_left.next;
            pre_left.next = node_to_move;
        }

        return dummy.next;
    }
}