Reverse Linked List II solution and explanation
Infosys
Google
9 more videos on this problem
Reverse Linked List II - Leetcode 92 - PythonNeetCode · 16:03 · 132K views
Reverse Linked List 2 (LeetCode 92) | Full simplified solution | Animations and DemoNikhil Lohia · 19:31 · 54K views
LeetCode Reverse Linked List II Solution Explained - JavaNick White · 8:34 · 39K views
Reverse Linked List II | Clean Approach | Dry Run | MICROSOFT | Leetcode - 92 | codestorywithMIKcodestorywithMIK · 21:53 · 26K views
LeetCode 92 | Reverse Linked List IIleetuition · 8:05 · 12K views
Master LeetCode 92: Reverse Linked List II | Step-by-Step Guide & TipsEngineering Digest · 13:47 · 9K views
[Java] Leetcode 92. Reverse Linked List II [LinkedList Reversal #2]Eric Programming · 14:41 · 4K views
Reverse Linked List II LeetCode 92 JavaScript O(N) solution. GitHub repo below.Team Evan Codes · 12:59 · 1K views
Can You Reverse a Linked List? (LeetCode 92: Reverse Linked List II)Code With Zi · 7:52 · 778 views
Reverse Linked List II - Leetcode 92 | Java + Step-by-Step Guide |Data Structures & AlgorithmsCode D Code · 5:41 · 657 views
The problem
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5]
Example 2:
Input: head = [5], left = 1, right = 1 Output: [5]
Constraints:
- The number of nodes in the list is
n. 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
Approach overview
Problem Overview: Reverse a section of a singly linked list between positions left and right (1-indexed) while keeping the rest of the list unchanged. The challenge is updating pointers correctly so the reversed sublist reconnects with the original list.
Approach 1: Iterative In-Place Reversal (O(n) time, O(1) space)
This approach walks the list once and reverses only the portion between left and right. First, iterate to the node just before the reversal region using a pointer like prev. From there, perform an in-place reversal using the classic linked list reversal technique: repeatedly move the next node in the segment to the front of the sublist. The key insight is that you do not reverse the entire list; you only manipulate pointers within the specified window while keeping track of the connection points before and after the segment.
A dummy node simplifies edge cases where the reversal starts at the head. During each iteration, you detach the next node and insert it at the beginning of the reversed portion. This effectively builds the reversed sublist while preserving constant extra memory. Since every node is visited at most once, the time complexity is O(n) and the space complexity remains O(1). This method is the most common implementation expected in interviews involving linked list pointer manipulation.
Approach 2: Recursive In-Place Reversal (O(n) time, O(n) space)
The recursive strategy breaks the problem into two smaller tasks: moving the head of the list until it reaches the left boundary, then reversing the next right - left + 1 nodes recursively. A helper function performs the reversal of the first k nodes and returns the new head of that reversed segment. During recursion unwinding, pointers reconnect the reversed segment with the remaining list.
This technique relies on the call stack to keep track of previous nodes, which introduces O(n) auxiliary space due to recursion depth. The advantage is conceptual clarity—once you define a function that reverses the first k nodes, the rest of the logic becomes straightforward. Problems that involve partial reversal often combine recursion with pointer tracking, making this a useful pattern when practicing recursion on linked structures.
Recommended for interviews: The iterative in-place reversal is what most interviewers expect. It runs in O(n) time with O(1) space and demonstrates strong pointer control in linked lists. The recursive solution shows conceptual understanding but uses additional stack space. Explaining both approaches—starting with the straightforward recursive idea and then optimizing to the iterative constant-space version—demonstrates strong problem-solving depth.
Approach 1: Iterative In-Place Reversal
This approach involves reversing the sublist in place by iterating from the left to the right node. We will use a dummy node to ensure that edge cases where the reversal starts at the head of the list are handled smoothly. During the iteration, we carefully manipulate the pointers to reverse the section of the list between the given positions.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
if not head:
return None
dummy = ListNode(0)
dummy.next = head
prev = dummy
for _ in range(left - 1):
prev = prev.next
start = prev.next
then = start.next
for _ in range(right - left):
start.next = then.next
then.next = prev.next
prev.next = then
then = start.next
return dummy.nextpublic class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (head == null) return null;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
for (int i = 0; i < left - 1; i++)
prev = prev.next;
ListNode start = prev.next;
ListNode then = start.next;
for (int i = 0; i < right - left; i++) {
start.next = then.next;
then.next = prev.next;
prev.next = then;
then = start.next;
}
return dummy.next;
}
}class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (!head) return nullptr;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;
for (int i = 0; i < left - 1; ++i)
prev = prev->next;
ListNode* start = prev->next;
ListNode* then = start->next;
for (int i = 0; i < right - left; ++i) {
start->next = then->next;
then->next = prev->next;
prev->next = then;
then = start->next;
}
return dummy->next;
}
};function ListNode(val, next=null) {
this.val = val;
this.next = next;
}
var reverseBetween = function(head, left, right) {
if (head === null) return null;
let dummy = new ListNode(0);
dummy.next = head;
let prev = dummy;
for (let i = 0; i < left - 1; i++) {
prev = prev.next;
}
let start = prev.next;
let then = start.next;
for (let i = 0; i < right - left; i++) {
start.next = then.next;
then.next = prev.next;
prev.next = then;
then = start.next;
}
return dummy.next;
};#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (!head) return NULL;
ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
dummy->val = 0;
dummy->next = head;
ListNode* prev = dummy;
for (int i = 0; i < left - 1; ++i)
prev = prev->next;
ListNode* start = prev->next;
ListNode* then = start->next;
for (int i = 0; i < right - left; ++i) {
start->next = then->next;
then->next = prev->next;
prev->next = then;
then = start->next;
}
head = dummy->next;
free(dummy);
return head;
}public class Solution {
public ListNode ReverseBetween(ListNode head, int left, int right) {
if (head == null) return null;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
for (int i = 0; i < left - 1; i++)
prev = prev.next;
ListNode start = prev.next;
ListNode then = start.next;
for (int i = 0; i < right - left; i++) {
start.next = then.next;
then.next = prev.next;
prev.next = then;
then = start.next;
}
return dummy.next;
}
}The code initializes a ListNode class to represent each node. The reverseBetween method begins by creating a dummy node that precedes the head of the list, which allows us to manage edge cases where the head itself needs modification.
We identify the node before the left position, referred to as prev, and initiate a standard pointer reversal technique for the sublist. This involves switching the next pointers within the range of left and right to achieve the desired reversal.
Time Complexity: O(n), where n is the number of nodes in the list. We do a single pass over the list between left and right.
Space Complexity: O(1), since no additional data structures are used.
Approach 2: Recursive In-Place Reversal
In this approach, we leverage recursion to reverse the sublist between the given positions. The primary idea is to handle the reversal within the recursive call stack, ensuring the in-place modification of the linked list while managing the sublist reversal inherently through recursive stack control.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
def reverse(first: ListNode, n: int) -> ListNode:
if n == 1:
self.successor = first.next
return first
last = reverse(first.next, n - 1)
first.next.next = first
first.next = self.successor
return last
self.successor = None
if left == 1:
return reverse(head, right)
head.next = self.reverseBetween(head.next, left - 1, right - 1)
return headHere, we define a recursive inner function reverse which handles the reversal of the initial segment of the list up to the right-left position. The recursion unfolds with the base case for n = 1. The main function drive adjusts to skip the initial non-reversal nodes as needed before invoking the recursive calls.
Time Complexity: O(n), where n is the total number of nodes in the list.
Space Complexity: O(n), due to recursive call stack depth based on n.
Approach 3: Simulation
Define a dummy head node dummy, pointing to the head node head of the linked list. Then define a pointer pre pointing to dummy. Start traversing the linked list from the dummy head node. When you traverse to the left node, point pre to this node. Then start traversing right - left + 1 times from this node, and insert the nodes you traverse into the back of pre. Finally, return dummy.next.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the linked list.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
const n = right - left;
if (n === 0) {
return head;
}
const dummy = new ListNode(0, head);
let pre = null;
let cur = dummy;
for (let i = 0; i < left; i++) {
pre = cur;
cur = cur.next;
}
const h = pre;
pre = null;
for (let i = 0; i <= n; i++) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
h.next.next = cur;
h.next = pre;
return dummy.next;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, left int, right int) *ListNode {
if head.Next == nil || left == right {
return head
}
dummy := &ListNode{0, head}
pre := dummy
for i := 0; i < left-1; i++ {
pre = pre.Next
}
p, q := pre, pre.Next
cur := q
for i := 0; i < right-left+1; i++ {
t := cur.Next
cur.Next = pre
pre = cur
cur = t
}
p.Next = pre
q.Next = cur
return dummy.Next
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn reverse_between(
head: Option<Box<ListNode>>,
left: i32,
right: i32,
) -> Option<Box<ListNode>> {
let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
let mut pre = &mut dummy;
for _ in 1..left {
pre = &mut pre.as_mut().unwrap().next;
}
let mut cur = pre.as_mut().unwrap().next.take();
for _ in 0..right - left + 1 {
let mut next = cur.as_mut().unwrap().next.take();
cur.as_mut().unwrap().next = pre.as_mut().unwrap().next.take();
pre.as_mut().unwrap().next = cur.take();
cur = next;
}
for _ in 0..right - left + 1 {
pre = &mut pre.as_mut().unwrap().next;
}
pre.as_mut().unwrap().next = cur;
dummy.unwrap().next
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative In-Place Reversal | Time Complexity: O(n), where n is the number of nodes in the list. We do a single pass over the list between left and right. |
| Recursive In-Place Reversal | Time Complexity: O(n), where n is the total number of nodes in the list. |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative In-Place Reversal | O(n) | O(1) | Best general solution; optimal for interviews and large lists with strict memory constraints |
| Recursive In-Place Reversal | O(n) | O(n) | Useful for understanding recursive linked list reversal patterns or practicing recursion techniques |
Frequently asked questions
Is Reverse Linked List II easy or hard?
Reverse Linked List II is considered a Medium difficulty problem. The challenge comes from correctly updating multiple pointers while reversing only a portion of the list, especially handling edge cases when the reversal starts at the head.
Reverse Linked List II Python/Java solution
Python and Java implementations follow the same logic: locate the node before the left boundary, then iteratively move nodes from the sublist to the front to reverse the segment. The algorithm maintains O(n) time complexity and O(1) additional space across both languages.
How to solve Reverse Linked List II in O(n)?
Traverse the list until reaching the node just before the left position. Then iteratively reverse nodes between left and right by adjusting next pointers and inserting each node at the front of the sublist. This performs the reversal in one pass, resulting in O(n) time and O(1) space complexity.
What is the best approach for Reverse Linked List II?
The best approach is the iterative in-place reversal technique. It reverses only the nodes between the left and right positions while keeping the rest of the list intact. This method runs in O(n) time and uses O(1) extra space, which makes it the optimal and most commonly expected solution in coding interviews.
Is Reverse Linked List II asked at Google/Amazon/Meta?
Reverse Linked List II is a common linked list interview problem and variations have appeared in interviews at companies like Amazon, Meta, and Google. Interviewers use it to evaluate pointer manipulation skills and understanding of partial list reversal.
What data structure is used in Reverse Linked List II?
The problem uses a singly linked list. The solution relies on pointer manipulation—tracking nodes before the reversal segment, reversing links within the segment, and reconnecting the modified portion back to the original list.
What is the time complexity of Reverse Linked List II?
The optimal solution runs in O(n) time because the algorithm traverses the linked list at most once. Pointer updates during the reversal are constant-time operations. The iterative method uses O(1) extra space, while the recursive version uses O(n) space due to the recursion stack.