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:
n.1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= nThe key challenge in Reverse Linked List II is reversing only a specific portion of a singly linked list while keeping the rest of the list unchanged. The common approach is to traverse the list until reaching the starting position of the sublist and then perform an in-place reversal.
A practical strategy is to use a dummy node to simplify edge cases (such as when the head is part of the reversed segment). Once the node just before the left boundary is located, iteratively reverse pointers within the range using standard linked list reversal techniques. After reversing the required section, reconnect the reversed portion back to the original list.
This method avoids extra data structures and works directly with pointers, making it efficient for interview settings. The traversal happens once, and only pointer adjustments are required, resulting in O(n) time complexity and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| In-place sublist reversal using pointer manipulation | O(n) | O(1) |
NeetCode
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.
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.
1class Solution {
2public:
3 ListNode* reverseBetween(ListNode* head, int left, int right) {
4 if (!head) return nullptr;
5
6 ListNode* dummy = new ListNode(0);
7 dummy->next = head;
8 ListNode* prev = dummy;
9
10 for (int i = 0; i < left - 1; ++i)
11 prev = prev->next;
12
13 ListNode* start = prev->next;
14 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 C++ solution follows similar logic to the previous solutions, maintaining the use of a dummy node to facilitate smooth operation even at the left boundary. The loop structure ensures an efficient in-place reversal through targeted pointer updates.
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.
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.
1class ListNode:
2 def __init__(self, val=0, next=
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of linked list reversal problems are commonly asked in FAANG and other top tech interviews. They test understanding of pointer manipulation, edge case handling, and in-place data structure modification.
A dummy node simplifies handling edge cases, especially when the reversal starts at the head of the list. It ensures consistent pointer management and avoids special-case logic when reconnecting the reversed segment.
A singly linked list is the primary data structure used in this problem. Efficient pointer manipulation within the linked list allows you to reverse a portion of the list without using additional data structures.
The optimal approach is to reverse the specified portion of the list in place using pointer manipulation. By locating the node before the left boundary and iteratively reversing nodes until the right boundary, the list can be modified in one pass with constant extra space.
Here, 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.