Reverse Linked List II
Reverse Linked List II is a medium linked list problem solved with the front middle back pointer pattern.
The best approach, optimal (front insertion, one pass), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, from collect values and write back up.
Problem
Reverse the nodes of a linked list from position left to position right (1-indexed, inclusive) and return the head. Nodes outside that range stay where they are.
Examples
Example 1
- Input
head = [1, 2, 3, 4, 5], left = 2, right = 4- Output
[1, 4, 3, 2, 5]
Example 2
- Input
head = [7, 8], left = 1, right = 2- Output
[8, 7]
Constraints
1 <= left <= right <= n <= 500- Follow-up: one pass.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Collect values and write back | O(n) | O(n) |
| Optimal (front insertion, one pass) | O(n) | O(1) |
1Collect values and write back
O(n)O(n)Copy the values in positions left..right into a list, then write them back in reverse.
- Walk to position left, collect right - left + 1 values.
- Walk again and overwrite them in reverse order.
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
List<Integer> vals = new ArrayList<>();
ListNode p = head;
for (int i = 1; i < left; i++) p = p.next;
ListNode start = p;
for (int i = left; i <= right; i++) { vals.add(p.val); p = p.next; }
p = start;
for (int i = vals.size() - 1; i >= 0; i--) { p.val = vals.get(i); p = p.next; }
return head;
}
}2Optimal (front insertion, one pass)
O(n)O(1)prev is the node before position left and cur is the first node of the sublist. Take the node after cur and move it right after prev, right - left times. cur slides toward the end and the sublist comes out reversed.
- Dummy node; move prev left - 1 steps; cur = prev.next.
- Repeat right - left times: move = cur.next; cur.next = move.next; move.next = prev.next; prev.next = move.
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0, head), prev = dummy;
for (int i = 1; i < left; i++) prev = prev.next;
ListNode cur = prev.next;
for (int i = 0; i < right - left; i++) {
ListNode move = cur.next;
cur.next = move.next;
move.next = prev.next;
prev.next = move;
}
return dummy.next;
}
}Edge cases to test
- left = 1 (the head changes)
- left == right (nothing changes)
Hints
Hint 1
Stop at the node before position left. Then repeatedly move the node after the current one to the front of the sublist.
FAQ
What is the best time complexity for Reverse Linked List II?
Optimal (front insertion, one pass) runs in O(n) time and O(1) extra space.
Which pattern does Reverse Linked List II use?
It is a linked list problem that uses the front middle back pointer pattern. Other problems with the same pattern: Reverse Linked List, Reverse Nodes in k-Group, Palindrome Linked List.
Is there a brute force solution for Reverse Linked List II?
Yes. Collect values and write back takes O(n) time and O(n) space. Copy the values in positions left..right into a list, then write them back in reverse.
Which edge cases should I test for Reverse Linked List II?
left = 1 (the head changes); left == right (nothing changes).