LeetCode 92 — Reverse Linked List II

What does it solve?

Given a linked list and two positions left and right (1-indexed), reverse only the nodes between those positions — leaving the rest of the list untouched — in one pass.

We use a dummy head trick so we never have to special-case reversing from the very start. We walk to the node just before left (call it prev), then use the "front-insertion" technique to pull nodes one at a time from the sublist and insert them right after prev.

The core idea (front-insertion)

// dummy → ... → prev → curr → ...
for i = 0 to right-left-1:
  nxt = curr.next
  curr.next = nxt.next // detach nxt
  nxt.next = prev.next // nxt points to sub-head
  prev.next = nxt       // insert nxt after prev

Complexity

Time complexity

O(N)

Walk to position left in O(left) and perform (right − left) front-insertions — total one pass through the list.

Space complexity

O(1)

Only a dummy node and three pointer variables. No extra memory needed regardless of list size.

Examples & edge cases

Live animation — front-insertion reversal

Untouched node prev anchor curr (tail of reversed so far) nxt (being inserted) Reversed region Done

Before

After (so far)

prev → — curr → — nxt → — iter: —

Step — of —

prev (anchor)

—

val: —

curr (tail)

—

val: —

nxt (inserting)

—

val: —

Iteration

—

of —

Select an example and press Play to start.

✓ Reversed

Speed Medium

Step-by-step table

Step	Phase	prev idx	curr idx	nxt idx	Action	List state

C++ implementation

reverse_list_ii.cpp

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* prev = &dummy;

    // step 1: walk prev to node just before position left
    for (int i = 1; i < left; i++)
        prev = prev->next;

    ListNode* curr = prev->next; // curr = node at position left

    // step 2: front-insertion (right − left) times
    for (int i = 0; i < right - left; i++) {
        ListNode* nxt = curr->next;
        curr->next = nxt->next;  // detach nxt from chain
        nxt->next  = prev->next; // nxt points to current sub-head
        prev->next = nxt;        // nxt becomes new sub-head
    }

    return dummy.next;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars