Reverse Linked List II

66.1k
0

Given the head of a singly linked list and two integers left and right, reverse the nodes from position left to position right. Positions are one-indexed. Return the head of the modified linked list.

The reversal must affect only nodes inside the selected range. Nodes before left and after right must keep the same relative order.

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] gets reversed to [4, 3, 2].

Example 2

Input: head = [1, 2, 3], left = 5, right = 6

Output: [1, 2, 3]

Explanation: Position 5 does not exist in the linked list, so no reversal is performed.

Brute Force Approach

In this approach, we keep the linked list structure unchanged and reverse only the values within the specified range. We first traverse the linked list and collect the values from positions left to right into an array.

After collecting the values, we reverse the array. Then, we traverse the linked list again and overwrite the values of the nodes in the same range using the reversed array.

Algorithm

  • Create an empty array to store the values from positions left to right, as the array makes it convenient to reverse only the selected portion.

  • Traverse the linked list with a position counter and collect the node values within the target range, so values outside the range remain untouched.

  • Reverse the collected array, since the required operation is to reverse the order of values between left and right.

  • Reset the traversal pointer to head, as the reversed values now need to be written back into their original positions.

  • Traverse the linked list again and replace the values from positions left to right with the corresponding reversed values, which updates only the selected portion.

  • Continue until all values in the selected range have been rewritten, while the linked-list connections remain unchanged.

  • Return the original head, as only the node values within the specified range have been modified.

Dry Run

rev ll II brute

rev ll II brute

Solution

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int data;
ListNode* next;
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
// Reverse the node values between positions left and right.
// The linked-list structure remains unchanged.
ListNode* reverseBetween(ListNode* head, int left, int right) {
vector<int> values;
ListNode* curr = head;
int pos = 1;
// Traverse the list and collect values from the target range.
// Values outside [left, right] are ignored.
while (curr != nullptr) {
if (pos >= left && pos <= right) {
values.push_back(curr->data);
}
curr = curr->next;
pos++;
}
// Reverse the collected values so they can be written
// back to the same nodes in the opposite order.
reverse(values.begin(), values.end());
// Start again from the head to update the selected nodes.
curr = head;
pos = 1;
int index = 0;
// Replace each value in the target range with its
// corresponding reversed value from the array.
while (curr != nullptr) {
if (pos >= left && pos <= right) {
curr->data = values[index++];
}
curr = curr->next;
pos++;
}
// Return the original head because only node values changed.
return head;
}
};
// Helper function to create a linked list from the given values.
ListNode* buildList(vector<int>& values) {
ListNode dummy(0);
ListNode* tail = &dummy;
// Create each node and connect it to the previous node.
for (int value : values) {
tail->next = new ListNode(value);
tail = tail->next;
}
// Return the first actual node of the list.
return dummy.next;
}
// Helper function to print the linked list in array format.
void printList(ListNode* head) {
cout << "[";
while (head != nullptr) {
cout << head->data;
head = head->next;
if (head != nullptr) {
cout << ", ";
}
}
cout << "]";
}
// Driver code.
int main() {
vector<int> values = {1, 2, 3, 4, 5};
// Build the linked list: 1 -> 2 -> 3 -> 4 -> 5
ListNode* head = buildList(values);
Solution sol;
// Reverse values between positions 2 and 4:
// 1 -> 2 -> 3 -> 4 -> 5
// becomes
// 1 -> 4 -> 3 -> 2 -> 5
ListNode* ans = sol.reverseBetween(head, 2, 4);
printList(ans);
return 0;
}

Complexity Analysis

Time Complexity: O(N), the linked list is traversed to collect and rewrite the values, while reversing the selected range takes O(R − L + 1).

Space Complexity: O(R − L + 1), an array stores the values from positions L to R, where N is the total number of nodes and L, R define the reversal range.

Optimal Approach

In this approach, we reverse the selected sublist directly by changing links. A dummy node is placed before the head so that cases where left = 1 can also be handled easily.

First, we move a pointer before to the node just before the reversal range. The first node of the range remains fixed as first. Then, we repeatedly take the node after first and insert it immediately after before. This moves nodes to the front of the selected range one by one, reversing only that part of the linked list.

Algorithm

  • Create a dummy node and connect it to the head, as this provides a node before the reversal range and makes the case left = 1 work with the same pointer logic.

  • Move a pointer before to the node immediately before position left, since this node will remain connected to the beginning of the reversed sublist.

  • Set first as the first node of the reversal range and curr as the node immediately after first, as these pointers identify the part that will be rearranged.

  • Repeat the process right - left times, since reversing a range of this length requires moving each following node to the front of the selected portion.

  • Detach curr from after first by updating first->next, which removes curr from its current position while keeping the remaining nodes connected.

  • Insert curr immediately after before, which moves the current node to the front of the selected range and gradually builds the reversed order.

  • Move curr to the next node after first, so the next node in the original order can be moved to the front in the same way.

  • Return dummy->next as the updated head, since the dummy node is only used to simplify the reversal and is not part of the final list.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int data;
ListNode* next;
// Create a linked list node with the given value.
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
// Reverse the links between positions left and right.
ListNode* reverseBetween(ListNode* head, int left, int right) {
// Dummy node handles cases where the reversal starts at the head.
ListNode dummy(0);
dummy.next = head;
// before points to the node immediately before the reversal range.
ListNode* before = &dummy;
// Move before to the node just before position left.
for (int pos = 1; pos < left; pos++) {
before = before->next;
}
// first remains at the beginning of the range throughout the reversal.
ListNode* first = before->next;
// curr points to the node that will be moved to the front next.
ListNode* curr = first->next;
// Move each following node to the front of the current reversed portion.
for (int step = 0; step < right - left; step++) {
// Remove curr from its current position.
first->next = curr->next;
// Insert curr immediately after before.
curr->next = before->next;
before->next = curr;
// Move curr to the next unreversed node.
curr = first->next;
}
// Return dummy.next because the original head may have changed.
return dummy.next;
}
};
// Helper creates a linked list from an array of values.
ListNode* buildList(vector<int>& values) {
ListNode dummy(0);
ListNode* tail = &dummy;
// Create each node and connect it to the previous node.
for (int value : values) {
tail->next = new ListNode(value);
tail = tail->next;
}
return dummy.next;
}
// Helper prints the linked list as an array.
void printList(ListNode* head) {
cout << "[";
while (head != nullptr) {
cout << head->data;
head = head->next;
if (head != nullptr) {
cout << ", ";
}
}
cout << "]";
}
// Driver code with a sample input.
int main() {
vector<int> values = {1, 2, 3, 4, 5};
ListNode* head = buildList(values);
Solution solution;
// Reverse the nodes from position 2 to position 4.
ListNode* answer = solution.reverseBetween(head, 2, 4);
printList(answer);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the total number of nodes in the linked list. The traversal moves through the required portion of the list a linear number of times.
Space Complexity: O(1), only a constant number of pointer variables are used, regardless of N.

Interview follow-up Questions

Yes. The dummy node handles left = 1 cleanly because the anchor becomes the dummy node.

Linked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Input: head = [1, 2, 3, 4] Output: [2, 1, 4, 3] Explanation: Pair (1, 2) becomes (2, 1) and pair (3, 4) becomes (4, 3) . Input: head = [1, 2, 3] Output: [2, 1, 3] Explanation: Last node remains unc...

59.8k
Linked List

Sort a Linked List Using Merge Sort

Given the head of a singly linked list, sort the linked list in non-decreasing order and return the head of the sorted linked list. Each node contains an integer value and a pointer to the next nod...

112.1k
Linked List

Find pairs with given sum in Doubly Linked List

Given a sorted doubly linked list containing positive distinct integers and an integer target, find every pair of node values whose sum equals target. Return pairs in increasing order based on the...

101.5k
Comments0