Reverse Linked List II
Medium · Linked Lists · Linked List
Problem
You are given the head of a singly linked list and two positions left <= right, counted from 1. Reverse only the nodes from position left through position right, and leave the rest of the list in place.
Rearrange the nodes themselves rather than only their values, and return the head of the modified list.
Can you do it in one pass?
Examples
Input: head = [10,20,30,40,50,60], left = 2, right = 5 Output: [10,50,40,30,20,60]
Positions 2 to 5 (20, 30, 40, 50) are reversed; 10 and 60 stay where they are.
Input: head = [7,8], left = 1, right = 2 Output: [8,7]
The block covers the whole list, so the head changes.
Input: head = [3], left = 1, right = 1 Output: [3]
Reversing a block of one node changes nothing.
Constraints
- The list has n nodes.
- 1 <= n <= 500
- -500 <= Node.val <= 500
- 1 <= left <= right <= n
Approaches
- Collect the nodes, reverse the slice, relink — time O(n), space O(n)
Follow-up
What if, instead of one block, you had to reverse every block of k nodes, or swap pairs of nodes? The same "node before the block" bookkeeping does it; see Reverse Nodes in k-Group and the use cases below.
Related problems
Start free on Cariara · Coding problems · System design studio
