Log inSign up
mediumLeetCodeNot Started

Reverse Linked List II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

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]
Explanation: Nodes from position 2 to 4 (values 2, 3, 4) are reversed to (4, 3, 2).

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]
Explanation: Single node sublist remains unchanged.

Constraints:

  • The number of nodes in the list is n.
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

1. Array Value Extraction and Sub-Array Reversal

Intuition

1. Collect node pointers or values into an array vals. 2. Reverse vals[left-1 .. right-1] using standard two pointers. 3. Traverse the linked list again, overwriting node.val with vals[i].

When to apply: Quick solution when value modification is acceptable or pointers are confusing.

Algorithm

  1. Traverse linked list and collect values in dynamic array.
  2. Reverse array elements in range [left - 1, right - 1].
  3. Traverse linked list again and write updated values.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode() : val(0), next(nullptr) {}
9 ListNode(int x) : val(x), next(nullptr) {}
10 ListNode(int x, ListNode *next) : val(x), next(next) {}
11};
12
13class Solution {
14public:
15 ListNode* reverseBetween(ListNode* head, int left, int right) {
16 std::vector<int> vals;
17 ListNode* curr = head;
18 while (curr != nullptr) {
19 vals.push_back(curr->val);
20 curr = curr->next;
21 }
22
23 std::reverse(vals.begin() + left - 1, vals.begin() + right);
24
25 curr = head;
26 for (int v : vals) {
27 curr->val = v;
28 curr = curr->next;
29 }
30 return head;
31 }
32};
33
34int main() {
35 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
36 Solution sol;
37 ListNode* res = sol.reverseBetween(head, 2, 4);
38 while (res != nullptr) {
39 std::cout << res->val << " ";
40 res = res->next;
41 }
42 std::cout << std::endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N) — Pass 1 extracts N values, reversing sub-array takes (right - left) / 2 steps, and pass 2 writes N values: O(N) overall.
  • Space complexity: O(N) — Stores N values in an auxiliary array: O(N) extra space.

2. Recursive Reversal of First N Nodes

Intuition

1. Base case: If left == 1, call reverseN(head, right) which reverses the first right nodes of a list and connects the tail to the remaining unreversed successor. 2. Recursive step: head.next = reverseBetween(head.next, left - 1, right - 1), return head.

When to apply: Functional and recursive problem-solving approaches.

Algorithm

  1. If left == 1, return reverseN(head, right).
  2. Otherwise, recurse on head.next with left - 1 and right - 1.
  3. reverseN(head, n) reverses first n nodes recursively and keeps track of successor.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12private:
13 ListNode* successor = nullptr;
14
15 ListNode* reverseN(ListNode* head, int n) {
16 if (n == 1) {
17 successor = head->next;
18 return head;
19 }
20 ListNode* last = reverseN(head->next, n - 1);
21 head->next->next = head;
22 head->next = successor;
23 return last;
24 }
25
26public:
27 ListNode* reverseBetween(ListNode* head, int left, int right) {
28 if (left == 1) {
29 return reverseN(head, right);
30 }
31 head->next = reverseBetween(head->next, left - 1, right - 1);
32 return head;
33 }
34};
35
36int main() {
37 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
38 Solution sol;
39 ListNode* res = sol.reverseBetween(head, 2, 4);
40 while (res != nullptr) {
41 std::cout << res->val << " ";
42 res = res->next;
43 }
44 std::cout << std::endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N) — Visits each node in the prefix and sublist once: O(N) overall.
  • Space complexity: O(N) call stack — Recursion call stack depth reaches N in the worst case.

3. One-Pass In-Place Head-Insertion with Dummy Sentinel

Intuition

1. Create dummy sentinel dummy with dummy.next = head. 2. Traverse prev pointer left - 1 steps from dummy. 3. Let curr = prev.next (the start of the sublist). 4. Repeat right - left times: a. nxt = curr.next b. curr.next = nxt.next c. nxt.next = prev.next d. prev.next = nxt 5. Return dummy.next.

When to apply: The definitive, optimal O(1) space, single-pass algorithm demanded in technical interviews.

Algorithm

  1. Initialize sentinel dummy pointing to head.
  2. Advance prev pointer (left - 1) times.
  3. Set curr = prev.next.
  4. Iterate (right - left) times inserting curr.next immediately after prev.
  5. Return dummy.next.

Linked List Interactive Dry Run

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
prev is anchored at node 1
Visual state
Values and pointers at this exact step
linked list
This linked list trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Why this step matters

prev is anchored at node 1. curr is at node 2. We need to perform right - left = 2 head insertions.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12public:
13 ListNode* reverseBetween(ListNode* head, int left, int right) {
14 if (!head || left == right) return head;
15
16 ListNode dummy(0, head);
17 ListNode* prev = &dummy;
18
19 for (int i = 0; i < left - 1; ++i) {
20 prev = prev->next;
21 }
22
23 ListNode* curr = prev->next;
24 for (int i = 0; i < right - left; ++i) {
25 ListNode* nxt = curr->next;
26 curr->next = nxt->next;
27 nxt->next = prev->next;
28 prev->next = nxt;
29 }
30
31 return dummy.next;
32 }
33};
34
35int main() {
36 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
37 Solution sol;
38 ListNode* res = sol.reverseBetween(head, 2, 4);
39 while (res != nullptr) {
40 std::cout << res->val << " ";
41 res = res->next;
42 }
43 std::cout << std::endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N) single pass — Traverses at most right nodes (at most N steps) in a single linear pass.
  • Space complexity: O(1) auxiliary — Only uses 3 pointer variables (prev, curr, nxt): O(1) auxiliary space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Array Value Extraction and Sub-Array ReversalO(N)O(N)Extract all node values into an array, reverse the sub-array from index left - 1 to right - 1, and write the values back into the list.High time complexity
2.Recursive Reversal of First N NodesO(N)O(N) call stackRecursively advance to the left position, then invoke a helper function that reverses the first (right - left + 1) nodes.—
3.One-Pass In-Place Head-Insertion with Dummy SentinelOptimalO(N) single passO(1) auxiliaryAnchor pointer prev before index left. Iteratively pluck curr.next and insert it immediately after prev for right - left times.—

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Setting nxt.next = curr instead of nxt.next = prev.next: in head-insertion, new nodes must be inserted before the *entire* reversed prefix, not just curr.

Pitfall 2:

Forgetting to use a dummy node: when left == 1, head itself changes, causing bugs if prev starts at head.

Pitfall 3:

Advancing curr = curr.next in the loop: curr automatically shifts towards the end as nodes after it are plucked and inserted in front.

Back to DSA Sheet