Skip to main content
CodePeetCodePeet
CodePeet 250

Reverse Linked List II

MEDIUMProblemSolveExternal Links

Description

You are given the head of a singly linked list and two integers left and right, where left <= right. Your task is to reverse the nodes of the list from position left to position right (1-indexed), and return the modified list.

The nodes before position left and after position right should remain in their original order. Only the sub-portion of the list between positions left and right (inclusive) gets reversed.

For example, in the list 1 → 2 → 3 → 4 → 5 with left=2 and right=4, the segment [2, 3, 4] is reversed to become [4, 3, 2], giving the result 1 → 4 → 3 → 2 → 5.

Examples

Example 1

Input: head = [1, 2, 3, 4, 5], left = 2, right = 4

Output: [1, 4, 3, 2, 5]

Explanation: The nodes at positions 2, 3, and 4 have values 2, 3, and 4 respectively. After reversing this segment, the order becomes 4, 3, 2. The node at position 1 (value 1) stays before the reversed segment, and the node at position 5 (value 5) stays after it. The final list is 1 → 4 → 3 → 2 → 5.

Example 2

Input: head = [5], left = 1, right = 1

Output: [5]

Explanation: The list has only one node, and we are asked to reverse from position 1 to position 1. Reversing a single node leaves it unchanged, so the output is the same as the input.

Example 3

Input: head = [1, 2, 3, 4, 5], left = 1, right = 5

Output: [5, 4, 3, 2, 1]

Explanation: When left=1 and right=5 (the entire list), the whole list gets reversed. This is equivalent to the basic "Reverse Linked List" problem.

Constraints

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

Editorial

Brute Force

Intuition

The simplest approach is to extract the values from the linked list, reverse just the portion from index left to right in a regular array, and then write the values back into the linked list nodes.

Think of it like rearranging books on a shelf. Instead of carefully swapping books in place, you take all the books off the shelf, rearrange the ones you need to reverse on a table, and then place them all back. It is wasteful in terms of extra space, but conceptually straightforward.

This approach separates the reversal logic from the linked list pointer manipulation, making it easier to reason about correctness.

Step-by-Step Explanation

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

Step 1: Traverse the linked list and extract all values into an array: values = [1, 2, 3, 4, 5].

Step 2: Identify the sub-array to reverse. Using 0-indexed positions: indices 1 to 3 (positions 2 to 4 in 1-indexed). Sub-array = [2, 3, 4].

Step 3: Reverse the sub-array: [2, 3, 4] becomes [4, 3, 2].

Step 4: Place the reversed sub-array back: values = [1, 4, 3, 2, 5].

Step 5: Traverse the linked list again and overwrite each node's value with the corresponding value from the array.

Step 6: The linked list now reads 1 → 4 → 3 → 2 → 5. Return the head.

Brute Force — Extract, Reverse, Write Back — Watch how we extract values to an array, reverse the targeted sub-section, and write the values back into the linked list nodes.

Algorithm

  1. Traverse the linked list and collect all node values into an array
  2. Reverse the portion of the array from index (left - 1) to index (right - 1)
  3. Traverse the linked list again, overwriting each node's value with the corresponding array value
  4. Return the head of the linked list

Code

/**
 * 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) {
        // Step 1: Extract values
        vector<int> values;
        ListNode* curr = head;
        while (curr) {
            values.push_back(curr->val);
            curr = curr->next;
        }
        
        // Step 2: Reverse the sub-array [left-1, right-1]
        int l = left - 1, r = right - 1;
        while (l < r) {
            swap(values[l], values[r]);
            l++;
            r--;
        }
        
        // Step 3: Write values back
        curr = head;
        int i = 0;
        while (curr) {
            curr->val = values[i++];
            curr = curr->next;
        }
        
        return head;
    }
};
# 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]:
        # Step 1: Extract values
        values = []
        curr = head
        while curr:
            values.append(curr.val)
            curr = curr.next
        
        # Step 2: Reverse the sub-array [left-1, right-1]
        l, r = left - 1, right - 1
        while l < r:
            values[l], values[r] = values[r], values[l]
            l += 1
            r -= 1
        
        # Step 3: Write values back
        curr = head
        i = 0
        while curr:
            curr.val = values[i]
            i += 1
            curr = curr.next
        
        return head
/**
 * 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) {
        // Step 1: Extract values
        List<Integer> values = new ArrayList<>();
        ListNode curr = head;
        while (curr != null) {
            values.add(curr.val);
            curr = curr.next;
        }
        
        // Step 2: Reverse the sub-array [left-1, right-1]
        int l = left - 1, r = right - 1;
        while (l < r) {
            int temp = values.get(l);
            values.set(l, values.get(r));
            values.set(r, temp);
            l++;
            r--;
        }
        
        // Step 3: Write values back
        curr = head;
        int i = 0;
        while (curr != null) {
            curr.val = values.get(i++);
            curr = curr.next;
        }
        
        return head;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the linked list twice (once to extract values, once to write them back), and reversing the sub-array takes O(right - left) time. All of these are linear in the size of the list, so total time is O(n).

Space Complexity: O(n)

We store all n node values in an auxiliary array. This extra space is the key weakness of this approach — we can do better.

Why This Approach Is Not Efficient

While the brute force runs in O(n) time, it uses O(n) extra space for the values array. This is unnecessary because linked list problems are designed to be solved by manipulating pointers directly — no extra array needed.

Additionally, this approach modifies node values rather than rearranging the actual nodes. In real-world scenarios, linked list nodes often carry complex data or are referenced by other structures, so changing their values can cause side effects. The correct approach is to rewire the next pointers to rearrange the nodes themselves.

The follow-up challenge asks: can you do it in one pass with O(1) space? The brute force uses two passes and O(n) space, falling short on both counts.

Optimal Approach - Iterative In-Place Pointer Reversal

Intuition

Instead of copying values, we can reverse the sub-list by rewiring the next pointers of the nodes directly. The key idea is to use a technique sometimes called "link reversal" or "front insertion".

Imagine you have a train with cars numbered 1 through 5, and you need to reverse cars 2, 3, and 4. Instead of lifting them all off the track, you keep car 2 as an anchor (it becomes the tail of the reversed segment) and repeatedly detach the car after it and move it to the front of the segment:

  • Start: 1 → 2 → 3 → 4 → 5
  • Detach 3, place before 2: 1 → 3 → 2 → 4 → 5
  • Detach 4, place before 3: 1 → 4 → 3 → 2 → 5

To implement this, we maintain three key pointers:

  • prev: the node just before the reversed segment (node 1 in our example). Its next pointer always points to the current front of the reversed segment.
  • tail: the node that was originally at position left (node 2). After reversal, it becomes the tail of the reversed segment. Its position in the list does not move — but its next pointer keeps shifting forward.
  • cache: the node we are about to detach and move to the front of the segment.

We use a dummy node before the head to handle the edge case where left = 1 (reversal starts at the head).

Diagram showing the iterative front-insertion pointer reversal technique on linked list 1→2→3→4→5 with left=2, right=4
Diagram showing the iterative front-insertion pointer reversal technique on linked list 1→2→3→4→5 with left=2, right=4

Step-by-Step Explanation

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

Step 1: Create a dummy node pointing to head. dummy → 1 → 2 → 3 → 4 → 5. Set prev = dummy.

Step 2: Move prev forward (left - 1 = 1) times. After one move: prev = node(1). Now prev points to the node just before position left.

Step 3: Set tail = prev.next = node(2). This is the node at position left. It will become the tail of the reversed segment after we are done.

Step 4 (Iteration 1 of reversal): We need to detach the node after tail and place it at the front of the segment.

  • cache = tail.next = node(3)
  • tail.next = cache.next → tail(2).next = node(4). Now: dummy → 1 → 2 → 4 → 5, and cache(3) is detached.
  • cache.next = prev.next → cache(3).next = node(2). Now cache points to the current front.
  • prev.next = cache → prev(1).next = node(3). Now: dummy → 1 → 3 → 2 → 4 → 5.

Step 5 (Iteration 2 of reversal): Again, detach the node after tail and place it at front.

  • cache = tail.next = node(4)
  • tail.next = cache.next → tail(2).next = node(5). Now: dummy → 1 → 3 → 2 → 5, and cache(4) is detached.
  • cache.next = prev.next → cache(4).next = node(3). Now cache points to current front.
  • prev.next = cache → prev(1).next = node(4). Now: dummy → 1 → 4 → 3 → 2 → 5.

Step 6: We performed (right - left) = 2 iterations. Reversal is complete. Return dummy.next = 1 → 4 → 3 → 2 → 5.

Iterative In-Place Reversal — Front Insertion Technique — Watch how we repeatedly detach the node after 'tail' and insert it at the front of the reversed segment, building the reversed order one node at a time.

Algorithm

  1. Create a dummy node pointing to head (handles edge case where left = 1)
  2. Move a pointer prev forward (left - 1) times so it points to the node just before position left
  3. Set tail = prev.next — this is the node at position left, which will become the tail of the reversed segment
  4. Repeat (right - left) times:
    a. Set cache = tail.next — the node to detach
    b. Set tail.next = cache.next — bypass cache in the chain
    c. Set cache.next = prev.next — point cache to the current front of the segment
    d. Set prev.next = cache — make cache the new front of the segment
  5. Return dummy.next

Code

/**
 * 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, head);
        ListNode* prev = &dummy;
        
        // Move prev to the node just before position 'left'
        for (int i = 0; i < left - 1; i++) {
            prev = prev->next;
        }
        
        ListNode* tail = prev->next;
        
        // Reverse the sublist by front-insertion
        for (int i = 0; i < right - left; i++) {
            ListNode* cache = tail->next;
            tail->next = cache->next;
            cache->next = prev->next;
            prev->next = cache;
        }
        
        return dummy.next;
    }
};
# 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 = ListNode(0, head)
        prev = dummy
        
        # Move prev to the node just before position 'left'
        for _ in range(left - 1):
            prev = prev.next
        
        tail = prev.next
        
        # Reverse the sublist by front-insertion
        for _ in range(right - left):
            cache = tail.next
            tail.next = cache.next
            cache.next = prev.next
            prev.next = cache
        
        return dummy.next
/**
 * 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;
        
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        
        // Move prev to the node just before position 'left'
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        
        ListNode tail = prev.next;
        
        // Reverse the sublist by front-insertion
        for (int i = 0; i < right - left; i++) {
            ListNode cache = tail.next;
            tail.next = cache.next;
            cache.next = prev.next;
            prev.next = cache;
        }
        
        return dummy.next;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse at most n nodes total: first we advance prev by (left - 1) steps, then we perform (right - left) reversal iterations. In the worst case (left=1, right=n), this is (0) + (n-1) = O(n) operations. Each reversal iteration does a constant amount of pointer manipulation.

Space Complexity: O(1)

We only use a constant number of extra pointers: dummy, prev, tail, and cache. No arrays, stacks, or recursive calls. This is a true in-place reversal that satisfies the follow-up challenge of doing it in one pass with O(1) space.