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, Python, C++ and JavaScript, 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.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
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 code in Java, Python, C++ and JavaScript.
| 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;
}
}class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
vals = []
p = head
for _ in range(1, left):
p = p.next
start = p
for _ in range(left, right + 1):
vals.append(p.val)
p = p.next
p = start
for i in range(len(vals) - 1, -1, -1):
p.val = vals[i]
p = p.next
return headclass Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
vector<int> vals;
ListNode* p = head;
for (int i = 1; i < left; i++) p = p->next;
ListNode* start = p;
for (int i = left; i <= right; i++) { vals.push_back(p->val); p = p->next; }
p = start;
for (int i = (int)vals.size() - 1; i >= 0; i--) { p->val = vals[i]; p = p->next; }
return head;
}
};function reverseBetween(head, left, right) {
const vals = [];
let p = head;
for (let i = 1; i < left; i++) p = p.next;
const start = p;
for (let i = left; i <= right; i++) { vals.push(p.val); p = p.next; }
p = start;
for (let i = vals.length - 1; i >= 0; i--) { p.val = vals[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;
}
}class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
prev = dummy
for _ in range(1, left):
prev = prev.next
cur = prev.next
for _ in range(right - left):
move = cur.next
cur.next = move.next
move.next = prev.next
prev.next = move
return dummy.nextclass Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(0, head);
ListNode* 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;
}
};function reverseBetween(head, left, right) {
const dummy = new ListNode(0, head);
let prev = dummy;
for (let i = 1; i < left; i++) prev = prev.next;
const cur = prev.next;
for (let i = 0; i < right - left; i++) {
const 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).