Reverse Linked List II — Solution in Python, Java & C++
Reverse Linked List II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on two pointers.
Reverse Linked List II is a medium coding problem on two pointers, asked in Amazon, Microsoft, Meta and Apple interviews.
- Difficulty: Medium
- Topics: Two Pointers
- Asked at: Amazon, Microsoft, Meta, Apple
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the head of a singly linked list and two integers left <= right, reverse the nodes from position left to position right (positions counted from 1), leaving the rest of the list as it is. Return the head of the list.
Example 1
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Explanation: The segment 2 → 3 → 4 becomes 4 → 3 → 2.
Example 2
Input: head = [5], left = 1, right = 1
Output: [5]
Example 3
Input: head = [3,5,8], left = 1, right = 3
Output: [8,5,3]
Explanation: The range can cover the whole list, head included.
Constraints
The number of nodes in the list is n1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
Follow-up: Could you do it in one pass?
Hints for Reverse Linked List II
Hint 1
Find the node just before position
left; everything before it stays put.Hint 2
Reverse the segment by repeatedly taking the node right after the segment's (moving) first node and moving it to the front of the segment.
Hint 3
That front insertion is three link changes per node, done
right - lefttimes. A dummy node in front of the head coversleft = 1.
How to solve Reverse Linked List II
Stand on the node before the segment (pre). The segment's first node cur will end up last; one by one, pull the node after cur out and insert it right after pre. After right - left moves the segment is reversed, in a single pass.
Approach
- Create a dummy node before
head; walkpreforwardleft - 1steps from the dummy. - Let
cur = pre.next(the first node of the segment). - Repeat
right - lefttimes:nxt = cur.next;cur.next = nxt.next;nxt.next = pre.next;pre.next = nxt. - Return
dummy.next.
Why it works
Each move takes the next unreversed node of the segment and places it at the segment's front, so after i moves the first i + 1 nodes of the segment appear in reverse order directly after pre, with cur linked to the rest. After right - left moves the whole segment is reversed and still attached on both sides.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- When
left = 1the head changes — returndummy.next, not the originalhead. curnever moves: it is always the segment's last node, and itsnextkeeps the tail attached.left == rightneeds no work; the loop runs zero times.
Reference solution
Python
from typing import Optional
def reverseBetween(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
pre = dummy
for _ in range(left - 1):
pre = pre.next
cur = pre.next
for _ in range(right - left):
nxt = cur.next
cur.next = nxt.next
nxt.next = pre.next
pre.next = nxt
return dummy.nextJava
public static ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0, head), pre = dummy;
for (int i = 1; i < left; i++) pre = pre.next;
ListNode cur = pre.next;
for (int j = 0; j < right - left; j++) {
ListNode nxt = cur.next;
cur.next = nxt.next;
nxt.next = pre.next;
pre.next = nxt;
}
return dummy.next;
}C++
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode dummy(0, head);
ListNode* pre = &dummy;
for (int i = 1; i < left; i++) pre = pre->next;
ListNode* cur = pre->next;
for (int j = 0; j < right - left; j++) {
ListNode* nxt = cur->next;
cur->next = nxt->next;
nxt->next = pre->next;
pre->next = nxt;
}
return dummy.next;
}JavaScript
var reverseBetween = function(head, left, right) {
var dummy = new ListNode(0, head), pre = dummy;
for (var i = 1; i < left; i++) pre = pre.next;
var cur = pre.next;
for (var j = 0; j < right - left; j++) {
var nxt = cur.next;
cur.next = nxt.next;
nxt.next = pre.next;
pre.next = nxt;
}
return dummy.next;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 165 two pointers problems · the whole catalogue
Learn the technique: Two Pointers Technique