92. Reverse Linked List II

MediumLinked Lists and Pointer ManipulationPointer manipulation with a dummy nodeIn-place sublist reversal by head insertion

Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right (1-indexed) and return the head. Do it in one pass.

Open official problem prompt ↗

In plain English

Reverse a contiguous run of nodes between two 1-indexed positions in a single pass without allocating new nodes.

Picture it like this

Like reversing a stretch of beads on a string by repeatedly sliding the bead just ahead back to the start of the stretch, one at a time.

Example

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Why: Reversing positions 2 through 4 (values 2,3,4) gives 4,3,2, leaving the ends 1 and 5 in place.

Constraints

The number of nodes is n1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n

Pattern lesson

See the pattern, then code

In-place sublist reversal by head insertion

↗

Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. Once you sit on the node prev just before the sublist, you can repeatedly pull the node after the current one to the front of the segment; doing this right - left times reverses the window without touching the rest.

New words, made simpleKnow these before the algorithm

prev: The fixed node immediately before the segment; every extracted node is inserted right after it.
Head insertion: Removing the node after curr and re-inserting it at the front of the segment, which incrementally reverses order.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Copy values to array

Uses extra memory and mutates values, which some variants forbid.

Store the segment values, reverse the array, write them back.

Time O(n)Space O(right-left)

Reverse segment then reconnect

Correct but needs careful bookkeeping of four boundary nodes.

Cut the segment out, reverse it with three pointers, and stitch the ends back.

Time O(n)Space O(1)

Best choiceHead-insertion in one pass

Single pass, constant space, and no separate reconnection step.

Repeatedly move curr.next to just after prev, reversing in place.

Time O(n)Space O(1)

The rule we keep true

Invariant

After each of the right-left insertions, curr is still the original first segment node (now sinking toward the back) and prev.next is the newest front of the reversed portion.

Why this is correct

Reasoning

Each iteration takes the node directly after curr and moves it to the front of the window; since curr stays fixed and always trails, after right-left moves every segment node has been pulled ahead of curr exactly the right number of times, producing full reversal while the outside links never change.

The algorithm in three movesSay these aloud before coding

1Attach a dummy before head to handle left = 1 uniformly

prev=node1, curr=node2

2Advance prev by left-1 steps to the node just before the segment

move 3 to front: 1 -> 3 -> 2 -> 4 -> 5

3Set curr to prev.next, the first node of the segment

move 4 to front: 1 -> 4 -> 3 -> 2 -> 5

4Right minus left times, detach curr.next and splice it directly after prev

5Return dummy.next

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readleft-1 = 1 step

2 · AskNode before segment?

3 · Update stateprev=node1, curr=node2

4 · ResultSegment is 2,3,4.

Key takeaway

Nodes at positions 2 to 4 are reversed by repeatedly inserting the next node right after prev.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-6Reach the boundary
Dummy plus left-1 hops put prev exactly before the segment, covering the left = 1 case.
2
Lines 7Fix curr
curr is the first segment node and stays fixed as later nodes are pulled in front of it.
3
Lines 8-12Head-insert loop
Each pass detaches curr.next and re-links it right after prev, reversing the window incrementally.
4
Lines 13Return
dummy.next is the head, correct even when the head itself moved.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

left equals right (no change)
left = 1 (segment includes the head)
right = n (segment includes the tail)
Whole list reversed when left=1, right=n

Common beginner mistakes

Advancing prev the wrong number of steps (left vs left-1)
Updating curr instead of keeping it fixed, which corrupts the insertion logic
Returning head instead of dummy.next when the head is inside the reversed segment

Check your understanding

Why does curr never move while nodes around it do?

Reverse Linked List II

Reverse Linked List II

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Linked Lists and Pointer Manipulation