What is the brute force approach and complexity for Reverse Linked List II?

Store the nodes in a vector, reverse positions left..right, relink with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Reverse Linked List II?

Dummy node, walk to position left − 1, move right − left nodes to the front of the range with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Reverse Linked List II?

Look for key signals in the prompt: "reverse positions left to right" indicates Only a middle range flips → find the node before the range and keep it as the anchor.; "the rest of the list stays" indicates Stitch both ends: prev points at the new front, and the old first node points at the node after the range.; "singly linked list" indicates We can't walk back to the node before the range, so keep prev and move the range's nodes to the front one at a time..

Reverse Linked List II

Medium·LeetCode #92Basic Anchor

LeetCode

Jump:

30-Second Mental ModelLinked List — Reversal (Sublist: find the node before the range, reverse exactly the range, then stitch both ends)

Complexity:O(N)→O(N)

Key Insight

Keep prev on the node just before the range, and cur on the first node of the range. Each step takes the node right after cur and puts it right after prev, at the front of the range. cur never moves, so the range fills up backwards. After right − left steps the range is reversed, and both ends have been stitched by the same moves.

Core Validity Invariant

The range is reversed once right − left moves are done. Each move puts one more node at the front of the range, so the range reads backwards, and cur sits just before the node at position right + 1.

Problem

You get the head of a singly linked list, plus two positions, left and right. Positions start at 1.

Reverse only the nodes from position left to position right. The nodes before left and after right stay where they are. Return the head of the new list.

Input

head, the first node of the list, and the two positions left and right (with left ≤ right).

Output

The head of the list after the range from left to right is reversed.

Example 1

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

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

Positions 2 to 4 hold 2, 3, 4. Reversed, they read 4, 3, 2. Nodes 1 and 5 stay where they are.

Example 2

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

Output: [5]

The range is the only node. Reversing one node changes nothing.

Constraints

• The list has between 1 and 500 nodes.
• -500 ≤ Node.val ≤ 500
• 1 ≤ left ≤ right ≤ n, where n is the number of nodes.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I reverse positions 2 to 4 of [1, 2, 3, 4, 5], which nodes change place, and which ones do not?
2.
Which node do I need to hold on to, so I can attach the reversed range back to the rest of the list?
3.
What is the node before position 1? Does a list always have one, and what does that mean for my code?
4.
Can I reverse the range by moving nodes, instead of copying values? Which node has to move each time?
5.
If the range has k nodes and its first node stays put, how many nodes actually need to move?

Brute force approach

Idea

Reversing a range with pointers is awkward, because each middle node has to be re-linked in the right order. An array makes it easy. Put every node into a vector, reverse the slice that covers positions left to right, then point each node at the next one in the vector.

Thinking process

1
In an array, reversing positions left to right is one std::reverse on the slice from index left − 1 to index right − 1.
2
A linked list can't be sliced, so first store every node in a vector.
3
After the slice is reversed, the vector holds the nodes in their new order. Link them again, one after the other.
4
Check it on [1, 2, 3, 4, 5] with left = 2, right = 4. The vector is [1, 2, 3, 4, 5]. Reversing indexes 1 to 3 gives [1, 4, 3, 2, 5], and linking the nodes in that order gives 1 → 4 → 3 → 2 → 5.

Code & Implementation

brute.cpp

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // Put every node into an array, in list order.
        vector<ListNode*> nodes;
        for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
            nodes.push_back(cur);
        }
        // Positions are 1-based, so the range left..right is indexes left-1 .. right-1.
        reverse(nodes.begin() + (left - 1), nodes.begin() + right);
        // Link the nodes again in their new order.
        for (size_t i = 0; i + 1 < nodes.size(); i++) {
            nodes[i]->next = nodes[i + 1];
        }
        nodes.back()->next = nullptr;
        return nodes[0];
    }
};

import java.util.*;

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) return null;
        // Put every node into an array, in list order.
        List<ListNode> nodes = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            nodes.add(cur);
        }
        // Positions are 1-based, so the range left..right is indexes left-1 .. right-1.
        Collections.reverse(nodes.subList(left - 1, right));
        // Link the nodes again in their new order.
        for (int i = 0; i + 1 < nodes.size(); i++) {
            nodes.get(i).next = nodes.get(i + 1);
        }
        nodes.get(nodes.size() - 1).next = null;
        return nodes.get(0);
    }
}

from typing import Optional, List, Dict, Tuple

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:
            return None
        # Put every node into an array, in list order.
        nodes: List[ListNode] = []
        cur = head
        while cur:
            nodes.append(cur)
            cur = cur.next
        # Positions are 1-based, so the range left..right is indexes left-1 .. right-1.
        nodes[left - 1:right] = nodes[left - 1:right][::-1]
        # Link the nodes again in their new order.
        for i in range(len(nodes) - 1):
            nodes[i].next = nodes[i + 1]
        nodes[-1].next = None
        return nodes[0]

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
    if (head === null) return null;
    // Put every node into an array, in list order.
    const nodes: ListNode[] = [];
    for (let cur: ListNode | null = head; cur !== null; cur = cur.next) {
        nodes.push(cur);
    }
    // Positions are 1-based, so the range left..right is indexes left-1 .. right-1.
    let l = left - 1;
    let r = right - 1;
    while (l < r) {
        const temp = nodes[l];
        nodes[l] = nodes[r];
        nodes[r] = temp;
        l++;
        r--;
    }
    // Link the nodes again in their new order.
    for (let i = 0; i + 1 < nodes.length; i++) {
        nodes[i].next = nodes[i + 1];
    }
    nodes[nodes.length - 1].next = null;
    return nodes[0];
}

Complexity

Time O(N)Space O(N)

Correct and easy to check. But it stores all n node pointers, even though the nodes already hold the links we need. The optimal approach uses a few pointers and moves the nodes in place.

Optimized approach

Idea

Start from brute force

The brute stores every node in a vector, so it can reverse a slice in one call. But the nodes already link to each other. The slice can be reversed by moving nodes in place.

Find the repeated work

The vector holds all n nodes, and the write-back re-links all n of them. Only the nodes from left to right change order. The nodes before the range are already correct, and the nodes after it just need to stay attached to the end of the range.

Define the state — what variables do I need?

dummy: A fake node in front of the head. Its `next` is the head. It gives position 1 a node before it, so `left = 1` needs no special case.
prev: The node just before the range (position `left − 1`). Its `next` always points at the front of the reversed part.
cur: The first node of the range. It never moves. The nodes after it are moved to the front, one at a time.
nxt: The node moved to the front in this step. It is saved before any link changes.

Define validity

Define the transitions — when does each pointer move, and why is it safe?

Before the range

prev = &dummy; move prev `left − 1` times

After this, prev is the last node we keep unchanged. The dummy means left = 1 also has a node before it.

Start of the range

cur = prev->next

cur is the first node of the range. It stays fixed, so it ends at the back of the range, linked to the node after right.

Each of the `right − left` moves

nxt = cur->next; cur->next = nxt->next; nxt->next = prev->next; prev->next = nxt;

Save nxt first. Then cur skips over it, nxt points at the old front, and prev points at nxt. The old front stays reachable through prev->next until the last line, so no node is lost.

After the loop

return dummy.next

When left = 1 the head changes. The dummy holds the new head in one fixed place.

What does the current window add to the answer?

Each move adds one node to the front of the reversed range. After right − left moves, the range holds right − left + 1 nodes in reverse order.

Code & Implementation

optimal.cpp

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // A dummy node in front of the head, so position 1 also has a node before it.
        ListNode dummy(0, head);

        // prev ends on the node just before position left. It keeps its place.
        ListNode* prev = &dummy;
        for (int i = 1; i < left; i++) {
            prev = prev->next;
        }

        // cur is the first node of the range. It never moves, so it ends at the back of the range.
        ListNode* cur = prev->next;

        // Each move takes the node after cur and puts it at the front of the range, right after prev.
        // The range has right - left + 1 nodes, and cur is already the last one, so we need right - left moves.
        for (int i = 0; i < right - left; i++) {
            ListNode* nxt = cur->next;   // save the node we are moving before any link changes
            cur->next = nxt->next;       // cur skips over nxt
            nxt->next = prev->next;      // nxt points at the old front of the range
            prev->next = nxt;            // prev points at nxt, so nxt is the new front
        }
        return dummy.next;
    }
};

import java.util.*;

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) {
        // A dummy node in front of the head, so position 1 also has a node before it.
        ListNode dummy = new ListNode(0, head);

        // prev ends on the node just before position left. It keeps its place.
        ListNode prev = dummy;
        for (int i = 1; i < left; i++) {
            prev = prev.next;
        }

        // cur is the first node of the range. It never moves, so it ends at the back of the range.
        ListNode cur = prev.next;

        // Each move takes the node after cur and puts it at the front of the range, right after prev.
        // The range has right - left + 1 nodes, and cur is already the last one, so we need right - left moves.
        for (int i = 0; i < right - left; i++) {
            ListNode nxt = cur.next;   // save the node we are moving before any link changes
            cur.next = nxt.next;       // cur skips over nxt
            nxt.next = prev.next;      // nxt points at the old front of the range
            prev.next = nxt;           // prev points at nxt, so nxt is the new front
        }
        return dummy.next;
    }
}

from typing import Optional, List, Dict, Tuple

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]:
        # A dummy node in front of the head, so position 1 also has a node before it.
        dummy = ListNode(0, head)

        # prev ends on the node just before position left. It keeps its place.
        prev = dummy
        for _ in range(1, left):
            if prev.next:
                prev = prev.next

        # cur is the first node of the range. It never moves, so it ends at the back of the range.
        cur = prev.next

        # Each move takes the node after cur and puts it at the front of the range, right after prev.
        # The range has right - left + 1 nodes, and cur is already the last one, so we need right - left moves.
        for _ in range(right - left):
            if cur and cur.next:
                nxt = cur.next       # save the node we are moving before any link changes
                cur.next = nxt.next   # cur skips over nxt
                nxt.next = prev.next  # nxt points at the old front of the range
                prev.next = nxt       # prev points at nxt, so nxt is the new front
        return dummy.next

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
    // A dummy node in front of the head, so position 1 also has a node before it.
    const dummy = new ListNode(0, head);

    // prev ends on the node just before position left. It keeps its place.
    let prev: ListNode = dummy;
    for (let i = 1; i < left; i++) {
        prev = prev.next!;
    }

    // cur is the first node of the range. It never moves, so it ends at the back of the range.
    const cur: ListNode = prev.next!;

    // Each move takes the node after cur and puts it at the front of the range, right after prev.
    // The range has right - left + 1 nodes, and cur is already the last one, so we need right - left moves.
    for (let i = 0; i < right - left; i++) {
        const nxt: ListNode = cur.next!; // save the node we are moving before any link changes
        cur.next = nxt.next;             // cur skips over nxt
        nxt.next = prev.next;            // nxt points at the old front of the range
        prev.next = nxt;                 // prev points at nxt, so nxt is the new front
    }
    return dummy.next;
}

Complexity

Time O(N)Space O(1)

Walking to position left − 1 costs up to N steps, and the moves cost right − left. Each node is touched a constant number of times, and only a few pointers are stored.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Store the nodes in a vector, reverse positions left..right, relink	O(N)	O(N)
Optimal	Dummy node, walk to position left − 1, move right − left nodes to the front of the range	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“reverse positions left to right”Only a middle range flips → find the node before the range and keep it as the anchor.
“the rest of the list stays”Stitch both ends: prev points at the new front, and the old first node points at the node after the range.
“singly linked list”We can't walk back to the node before the range, so keep prev and move the range's nodes to the front one at a time.

node before the range (prev)+move right − left nodes to the front of the range+stitch both ends→Linked List — Reversal (Sublist: find the node before the range, reverse exactly the range, then stitch both ends)

This is Reverse Linked List with the reversal limited to a range. The full version reverses everything, so it starts with prev = null, and the old tail becomes the new head. Here the nodes before left and after right must keep their places. So we start from a node in front of the range, and the range is attached back to the node after it. The next two questions in this sub-pattern reuse the anchor idea: Merge In Between swaps the range for another list, and Reverse Nodes in Even Length Groups repeats a sublist reversal on several groups.

Don't make this mistake

Reversing the whole list, like Reverse Linked List

✗ ListNode* prev = nullptr; for (ListNode* cur = head; cur != nullptr; ) { ... } // flips every node

✓ Walk to the node before `left`, then flip only `right − left + 1` nodes.

Pattern confusion: the full reversal starts with prev = null and flips every node in the list. On [1, 2, 3, 4, 5] with left = 2 and right = 4, it would give [5, 4, 3, 2, 1]. The right answer is [1, 4, 3, 2, 5]: node 1 stays before the range, and node 5 stays after it. Only the range may move, so the anchor node before it has to stay put.

Off by one on the range

✗ for (int i = 0; i < right - left + 1; i++) { ... } // one move too many

✓ for (int i = 0; i < right - left; i++) { ... }

The range has right − left + 1 nodes, but its first node (cur) stays in place. Only right − left nodes need to move. One extra move pulls the node after right into the range, so the list comes out wrong.

Changing the links in the wrong order

✗ prev->next = nxt; // the old front is lost here nxt->next = prev->next; // now nxt points at itself

✓ nxt->next = prev->next; // save the old front first prev->next = nxt;

prev->next is the only link to the old front of the range. If you overwrite it first, the old front and every node behind it are lost, and nxt ends up pointing at itself, which makes a cycle.

No node before position 1 when left = 1

✗ ListNode* prev = head; // when left = 1, prev is already inside the range for (int i = 1; i < left; i++) prev = prev->next;

✓ ListNode dummy(0, head); ListNode* prev = &dummy; // a node before position 1 always exists

When left = 1 the new head is a node inside the range, and nothing before it can point at the new head. The dummy gives every case a node to stitch onto, and return dummy.next returns the correct head.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Linked List — Reversal translate into production architectures and low-level memory mechanics.

LLD Architecture