DSA problem
Reverse Linked List II
Given the head of a singly linked list and two integers left and right where 1 <= left <= right <= n, reverse the nodes of the list from position left to position right (inclusive), and return the reversed list. Positions are 1-indexed, and the reversal must be done in a single pass and in place.
This is the windowed version of the classic linked list reversal. The tricky part is not the reversal itself — it is the bookkeeping at the boundaries. The node at position left - 1 is the "anchor": its next pointer eventually points to the reversed block. The node at position left becomes the tail of the reversed block, and its next must point at the node that was originally at position right + 1.
A robust technique is to prepend a dummy node before the head. The dummy guarantees that even when left = 1 — i.e. when the head itself gets reversed away — the anchor still exists, and the code path is uniform.
The optimal single-pass algorithm uses the front-splice (head-insertion) trick. Walk to the node just before left and call it prev. Let curr = prev.next be the first node of the window. Now perform right - left iterations: in each iteration, take curr.next (call it temp), splice it out, and re-insert it immediately after prev so it becomes the new front of the reversed segment. curr stays where it is and naturally drifts toward the tail of the window. After all iterations, the window from left to right is reversed in place. This solves the problem in O(n) time and O(1) extra space with a single traversal.
Examples
head = [1,2,3,4,5], left = 2, right = 4[1,4,3,2,5]head = [5], left = 1, right = 1[5]head = [3,5], left = 1, right = 2[5,3]Constraints
- The number of nodes in the list is n.
- 1 <= n <= 500
- -500 <= Node.val <= 500
- 1 <= left <= right <= n
- Follow up: Could you do it in one pass?
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.