Reverse Linked List II
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.
- The number of nodes in the list is n
- 1 ≤ n ≤ 500
- −500 ≤ Node.val ≤ 500
- 1 ≤ left ≤ right ≤ n
Example
head = [1,2,3,4,5], left = 2, right = 4[1,4,3,2,5]The brute-force approach would extract the sublist from position 2 to 4, reverse it separately, and then reattach it, which requires extra space and multiple passes. The optimal approach performs the reversal in-place during a single pass. Starting from the dummy node, the algorithm moves a pointer to the node before the reversal segment (position 1). It then iteratively reverses the links between nodes 2 to 4 by redirecting pointers, effectively reversing the sublist in-place. After the reversal, the sublist is reconnected to the rest of the list, preserving the original order outside the reversed segment.
Approach
Straightforward Solution
A naive solution extracts the sublist into an array or separate list, reverses it, and then reattaches it, resulting in O(n) time but O(k) space where k = right - left + 1.
Core Observation
Reversing a sublist in a singly linked list can be done by changing the next pointers of the nodes within the specified range, without creating new nodes or using extra space.
Path to Optimal
PreviewThe key insight is to perform the reversal in-place by iterating through the sublist once and reversing the next pointers as you go. Using a dummy node simplifies edge cases where the head is part of the reversed segment…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewCreate a dummy node pointing to head to handle edge cases. Move a pointer 'prev' to the node immediately before the reversal segment…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm traverses the list once to reach the node before the reversal segment and then iterates through the sublist once to reverse pointers, resulting in linear time proportional to the list length.
Space
O(1)
The reversal is done in-place by pointer manipulation without allocating extra data structures, using only a few pointer variables.
Pattern Spotlight
In-place Reversal of a Linked List (Partial Sublist)
When reversing a sublist within a singly linked list, use a dummy node to simplify edge cases and iteratively reverse pointers within the target range, reconnecting the reversed segment seamlessly to the unchanged parts.
Solution
| 1 | class Solution: |
| 2 | def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: |
| 3 | |
| 4 | dummy = ListNode(0, head) |
| 5 | prev = dummy |
| 6 | |
| 7 | for _ in range(left - 1): |
| 8 | prev = prev.next |
| 9 | |
| 10 | curr = prev.next |
| 11 | prev_node = None |
| 12 | |
| 13 | for _ in range(right - left + 1): |
| 14 | nxt = curr.next |
| 15 | curr.next = prev_node |
| 16 | prev_node = curr |
| 17 | curr = nxt |
| 18 | |
| 19 | tail = prev.next |
| 20 | prev.next = prev_node |
| 21 | tail.next = curr |
| 22 | |
| 23 | return dummy.next |
Step-by-Step Solution
Position Pointer Before Reversal Segment
| 4 | dummy = ListNode(0, head) |
| 5 | prev = dummy |
| 7 | for _ in range(left - 1): |
| 8 | prev = prev.next |
Objective
To locate the node immediately before the sublist that needs to be reversed.
Key Insight
Using a dummy node pointing to the head allows uniform handling of cases where the reversal starts at the head. Moving 'prev' forward left - 1 times positions it exactly before the reversal segment, setting up the reversal boundaries precisely.
Interview Quick-Check
Core Logic
Moving 'prev' left - 1 times ensures it points to the node before the reversal start, which is critical for reconnecting the reversed sublist later.
State & Boundaries
The loop runs exactly left - 1 times, which is safe because left >= 1 and the dummy node ensures 'prev' is never null.
Common Pitfalls & Bugs
Failing to use a dummy node can cause errors when left == 1, as there is no node before the head.
Reverse the Sublist In-Place by Pointer Rewiring
To reverse the nodes between positions left and right by changing their next pointers.
Reconnect the Reversed Sublist to the Main List
To link the reversed sublist back into the original list, preserving the overall list structure.
Return the New Head of the Modified List
To return the head of the updated list after the reversal operation.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
curr.next = prev_nodeReverse 'curr.next' to point to the previously reversed node.
This pointer reversal is the core operation that inverts the sublist links, enabling in-place reversal without extra space.
nxt = curr.nextStore the next node after 'curr' before changing pointers.
Preserving the next node before pointer reversal is critical to avoid losing the rest of the list, enabling safe in-place reversal.
prev.next = prev_nodeConnect 'prev.next' to the new head of the reversed sublist.
This reconnection is essential to maintain list integrity, ensuring the node before the reversed segment points to the new sublist head.
Full line-by-line criticality + rationale for all 15 lines available on Pro.
Test Your Understanding
Why is a dummy node used at the start of the list for this reversal algorithm?
See the answer with Pro.
Related Problems
In-place Reversal of a Linked List pattern
Don't just read it. Drill it.
Reconstruct Reverse Linked List II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Reverse Linked List II drill