Reverse Linked List II
Problem Statement
Given the head of a singly linked list and two positions left and right, reverse the nodes from position left through position right in place and return the modified list. Positions are 1-indexed, and the rest of the list must keep its original order.
Input
The head of a singly linked list and two 1-indexed positions left and right.
Output
The head of the same list after reversing only the segment from left to right.
Constraints
- •
The number of nodes is n - •
1 <= n <= 500 - •
-500 <= Node.val <= 500 - •
1 <= left <= right <= n
Examples
Example 1
head = 1 -> 2 -> 3 -> 4 -> 5, left = 2, right = 4
1 -> 4 -> 3 -> 2 -> 5Example 2
head = 1 -> 2 -> 3, left = 1, right = 2
2 -> 1 -> 3Learning Objectives
- Recognise sublist reversal as a boundary-reconnection problem, not just a full-list reversal.
- Use a dummy head to make reversing from position 1 behave like every other case.
- Apply head insertion to reverse a fixed segment in one pass.
- Track the node before the segment and the original segment head so both boundaries reconnect correctly.
Intuition
Pattern Recognition
The signal is a request to reverse only a contiguous part of a linked list. That means the hard part is not reversing pointers inside the segment; it is preserving the two outside boundaries. You need the node before left so the reversed segment can be attached back to the prefix, and you need the original left node because it becomes the tail of the reversed segment and must point to the suffix after right.
A dummy head removes the special case where left = 1. Once beforeSublist is positioned before left, the clean one-pass trick is head insertion: repeatedly detach the node immediately after sublistTail and insert it right after beforeSublist. Each insertion grows the reversed prefix of the segment while sublistTail remains the tail and keeps the suffix reachable.
Common mistakes
- ×Starting reversal at **left** without saving the node before it, which makes it impossible to attach the reversed segment to the prefix cleanly.
- ×Advancing **sublistTail** during head insertion; the original left node should stay as the segment tail.
- ×Forgetting to reconnect the segment tail to the node after **right**, which drops the suffix.
- ×Handling **left = 1** with separate fragile logic instead of using a dummy head.
Algorithm Explanation
Key idea
Keep beforeSublist on the node before position left and keep sublistTail on the original left node. Then repeat right - left times: take the node after sublistTail and insert it immediately after beforeSublist. This reverses the segment by front-loading nodes while the prefix and suffix remain reachable.
Pointer walkthrough
For head = 1 -> 2 -> 3 -> 4 -> 5, left = 2, and right = 4, start with dummy -> 1 -> 2 -> 3 -> 4 -> 5. Move beforeSublist to 1, so sublistTail is 2 and nodeToMove is 3. Detach 3 from after 2 and insert it after 1, producing dummy -> 1 -> 3 -> 2 -> 4 -> 5. Now nodeToMove is 4. Detach 4 and insert it after 1, producing dummy -> 1 -> 4 -> 3 -> 2 -> 5. The left boundary 1 points to the new segment head 4, and the segment tail 2 still points to the suffix 5.
Algorithm
- Create dummy and set dummy.next to head.
- Walk beforeSublist from dummy until it is immediately before position left.
- Set sublistTail = beforeSublist.next and nodeToMove = sublistTail.next.
- Repeat right - left times: detach nodeToMove, insert it after beforeSublist, and advance nodeToMove to sublistTail.next.
- Return dummy.next as the possibly new head.
Solutions
Solution: One-pass head insertion inside the sublist
Use a dummy head, walk to the node before the reversal window, then perform local head insertions within that window. Because each node is moved directly behind the left boundary, the segment reverses without needing an extra pass or an auxiliary stack.
Step-by-step
- Return early when left and right are the same because no pointer needs to change.
- Create dummy so the list has a stable node before the real head.
- Move beforeSublist exactly left - 1 times so it lands before the segment.
- Keep sublistTail on the original first node of the segment.
- For each remaining node in the segment, detach it from after sublistTail and insert it after beforeSublist.
- Return dummy.next after all boundary pointers have been updated.
O(n)
O(1)
The pointer walk and the in-place reversals touch each relevant node at most once while using a constant number of references.
Java implementation
Dry Run
Sample input
head = 1 -> 2 -> 3 -> 4 -> 5, left = 2, right = 4. Track the head-insertion moves after beforeSublist reaches node 1.
| move | beforeSublist | sublistTail | node moved | list state | boundary note |
|---|---|---|---|---|---|
| initial | 1 | 2 | none | dummy -> 1 -> 2 -> 3 -> 4 -> 5 | ready to move 3 after 1 |
| 1 | 1 | 2 | 3 | dummy -> 1 -> 3 -> 2 -> 4 -> 5 | 2 remains tail and points to 4 |
| 2 | 1 | 2 | 4 | dummy -> 1 -> 4 -> 3 -> 2 -> 5 | 2 reconnects to suffix 5 |
After right - left = 2 moves, the reversed segment is 4 -> 3 -> 2. Returning dummy.next gives 1 -> 4 -> 3 -> 2 -> 5.
Interview Tips
Name the two boundary pointers before writing code: beforeSublist and sublistTail. Interviewers watch whether you can reverse the middle without losing the suffix. Explain that sublistTail is intentionally not advanced during head insertion because it becomes the tail of the reversed segment.
Likely follow-ups
- How would you reverse several disjoint ranges in the same list?
- How would this change for a doubly linked list where **prev** pointers must also be fixed?
- Can you solve it recursively, and what stack space would that use?
- How would you validate **left** and **right** if the input positions were not guaranteed to be valid?
Similar Problems
Key Takeaways
- Sublist reversal is primarily a boundary-management problem.
- A dummy head makes reversal from the real head identical to reversal from the middle.
- Head insertion reverses a bounded segment while keeping the suffix reachable through the original segment head.
- The original **left** node becomes the tail of the reversed segment and must reconnect to the node after **right**.