Reverse Linked List II

The key idea

Reverse only the sublist between positions left and right in one pass. Hold a pointer to the node just before left so you can re-stitch the reversed segment back into the list; a dummy head makes the left = 1 case (reversing from the head) need no special branch.

Problem

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.

Positions are 1-indexed: the first node is at position 1. Only the nodes inside the window are reordered; everything before position left and after position right keeps its original place and links. Aim to do it in one pass.

Constraints

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

Examples

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

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

Input: head = [3,5,7,9], left = 1, right = 3 Output: [7,5,3,9]

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →