Reverse Linked List II

Explanation & Solution

Description

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, and return the reversed list.

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

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

Explanation: Nodes at positions 2 through 4 (values 2,3,4) are reversed to (4,3,2).

Constraints

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

Approach

In-Place Manipulation of a Linked List pattern

1. Create a Dummy Node

Create a dummy node pointing to head to handle the edge case where left = 1 (reversing from the head).
Move prev to the node just before position left.

2. Position the Pointers

Traverse left - 1 steps so prev is right before the reversal zone.
Set curr to prev.next — this is the first node in the sublist to reverse.

3. Reverse the Sublist

Iterate right - left times. In each iteration:
Save next = curr.next (the node to be moved to the front).
Remove next from its position: curr.next = next.next.
Insert next at the front of the reversed portion: next.next = prev.next.
Update the connection: prev.next = next.
After each iteration, one more node has been moved to the front of the sublist.

4. Return the Result

dummy.next is the new head (it may have changed if left = 1).
Collect values and return as an array.

🧠 Key Insight

The "pull node to front" technique avoids explicitly tracking the tail of the reversed sublist.
The dummy node eliminates special-casing the head.

Time

O(n)single pass through the list.

Space

O(1)only pointer variables used.

Visualization

Input:

Linked List Traversal

—

No animation available

Slow (S)Fast (F)Both

0 steps

Solution Code

Reverse Linked List

Reverse Nodes in k-Group