Pseudo-code:

text
function reverseBetween(head, left, right):
    nodes = []
    current = head
    position = 1
    
    // Collect nodes in the range
    while current:
        if position >= left and position <= right:
            nodes.push(current.val)
        current = current.next
        position++
        
    // Reverse the collected values
    reverse(nodes)
    
    // Write values back
    current = head
    position = 1
    index = 0
    while current:
        if position >= left and position <= right:
            current.val = nodes[index]
            index++
        current = current.next
        position++
        
    return head

Complexity Analysis:

• Time Complexity: $O(N)$ because we traverse the list twice (once to read, once to write).
• Space Complexity: $O(N)$ (specifically $O(right - left)$) to store the values in the array.

Why it fails: While this solution might pass within the time limits for $N=500$, it fails the spirit of the problem. The follow-up explicitly asks for a one-pass solution using $O(1)$ extra space. In an interview context, allocating an array to solve a linked list pointer problem is generally considered suboptimal because it bypasses the core challenge of pointer manipulation.

Core Insight for Reverse Linked List II

The key intuition for the optimal solution is to treat the sublist reversal as a sequence of "move to front" operations. Instead of reversing the pointers all at once or swapping values, we maintain a fixed reference to the node immediately before the sub-segment (let's call this prev) and the first node of the sub-segment (let's call this curr).

During the reversal process within the range [left, right], the curr node remains the same (it eventually becomes the tail of the reversed sublist). We iteratively take the node immediately following curr (let's call it next_node) and move it to the position right after prev.

The Invariant: At any step $k$ inside the loop, the sub-segment from left to left + k is reversed. We repeat this operation right - left times.

Visual Description: Imagine the list segment: A -> [B -> C -> D] -> E where we want to reverse B through D.

1. Initial State: prev points to A, curr points to B. next_node is C.
2. First Iteration: We detach C and insert it between A and B.
   • Result: A -> C -> B -> D -> E
3. Second Iteration: Now curr is still B. next_node becomes D. We detach D and insert it between A and C.
   • Result: A -> D -> C -> B -> E

By consistently moving the "next" node to the front of the sub-segment, we reverse the list in place with a single pass through the relevant nodes.

Execution Flow

Let's trace the algorithm with head = [1, 2, 3, 4, 5], left = 2, right = 4.

1. Setup:
   • Create dummy node with value 0. dummy.next points to 1.
   • prev starts at dummy.
2. Position prev:
   • Move prev forward left - 1 (1) time.
   • prev now points to node 1.
3. Initialize Reversal Pointers:
   • curr points to prev.next (node 2).
   • We need to perform right - left (4 - 2 = 2) reversal operations.
4. Loop 1:
   • next_node is curr.next (node 3).
   • Step A: curr.next = next_node.next (Node 2 points to 4).
   • Step B: next_node.next = prev.next (Node 3 points to 2).
   • Step C: prev.next = next_node (Node 1 points to 3).
   • Current List: 1 -> 3 -> 2 -> 4 -> 5
5. Loop 2:
   • curr is still node 2. next_node is now curr.next (node 4).
   • Step A: curr.next = next_node.next (Node 2 points to 5).
   • Step B: next_node.next = prev.next (Node 4 points to 3).
   • Step C: prev.next = next_node (Node 1 points to 4).
   • Current List: 1 -> 4 -> 3 -> 2 -> 5
6. Completion:
   • Loop finishes. Return dummy.next (node 1).
   • Final Output: [1, 4, 3, 2, 5].

Proof of Correctness

The correctness relies on the invariant that prev always points to the node immediately preceding the reversal group. The curr pointer acts as the anchor for the original start of the group.

In every iteration, we take the node curr.next and insert it between prev and prev.next. This effectively reverses the order of nodes processed so far relative to the prev node.

• If the list has size $N$ and we reverse from left to right, the pointers outside this range are never touched, preserving the rest of the list structure.
• The dummy node ensures that if left=1, prev is the dummy, and insertions happen at the true head of the list, correctly updating the head reference.

Reference Implementation

C++ Solution for LeetCode 92

cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (!head || left == right) return head;

        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;

        // Step 1: Move prev to the node just before the 'left' position
        for (int i = 0; i < left - 1; ++i) {
            prev = prev->next;
        }

        // Step 2: Reverse the sublist
        // curr: the first node of the sublist to be reversed
        ListNode* curr = prev->next;
        
        for (int i = 0; i < right - left; ++i) {
            ListNode* next_node = curr->next;
            
            // Rewire pointers
            curr->next = next_node->next;
            next_node->next = prev->next;
            prev->next = next_node;
        }

        return dummy.next;
    }
};

Java Solution for LeetCode 92

java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left == right) return head;

        // Dummy node to handle edge case where left = 1
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // Step 1: Reach the node just before the sublist
        ListNode prev = dummy;
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        
        // Step 2: Reverse the sublist
        ListNode curr = prev.next;
        for (int i = 0; i < right - left; i++) {
            ListNode nextNode = curr.next;
            
            // Pointer manipulation
            curr.next = nextNode.next;
            nextNode.next = prev.next;
            prev.next = nextNode;
        }
        
        return dummy.next;
    }
}

Python Solution for LeetCode 92

python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if not head or left == right:
            return head
        
        # Dummy node simplifies edge cases where head is modified
        dummy = ListNode(0, head)
        prev = dummy
        
        # Step 1: Move prev to position left - 1
        for _ in range(left - 1):
            prev = prev.next
            
        # Step 2: Reverse the sublist
        curr = prev.next
        for _ in range(right - left):
            next_node = curr.next
            
            # Pointer manipulation
            curr.next = next_node.next
            next_node.next = prev.next
            prev.next = next_node
            
        return dummy.next