1. Problem Summary
You are given the head of a singly linked list and two positions left and right (1-indexed, with left <= right).
You must reverse the nodes from position left to position right in-place, and return the head of the modified list.
Nodes before position left and after right must keep their relative order.
Input:
head: head node of a singly linked list
left, right: integers with 1 <= left <= right <= n
Output:
Head of the linked list after reversing the sublist [left, right]
Key constraints:
1 <= n <= 500
One-pass follow-up: do it with a single traversal of the list if possible.
2. Examples Explanation
Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4
Positions:
1 → 1
2 → 2
3 → 3
4 → 4
5 → 5
Reverse positions 2 to 4: sublist [2,3,4] becomes [4,3,2].
Final list: [1,4,3,2,5].
Example 2:
Input: head = [5], left = 1, right = 1
Only one node and the range is a single position. Reversing a single node does nothing.
Output remains [5].
3. Approach
Pattern:
This is a classic linked list in-place reversal of a sublist, using:
Pointer manipulation
One-pass traversal (follow-up requirement)
Naive / Simpler Ideas:
Extract + Reverse + Rebuild (using extra structure):
Copy nodes from left to right into an array, reverse, and then rebuild.
This is unnecessary and uses extra space O(k).
Two-pass approach:
First pass: find left, right nodes and their previous/next.
Second pass: reverse the sublist.
Still fine, but we can do better with a single pass pointer method.
4. Optimal Approach: In-place Sublist Reversal in One Pass
High-Level Idea:
We want to:
Walk the list until the node just before the left-th node (call it pre).
From there, reverse the sublist of length right - left + 1 using standard head-insertion technique.
Re-link the reversed sublist back into the main list.
Using a dummy node before head simplifies edge cases when left = 1.
Detailed Steps:
Create a dummy node pointing to head.
Move a pointer pre from dummy to the node just before position left.
After this loop, pre.next is the left-th node (start of sublist).
Let:
start = pre.next → first node of the sublist to reverse.
then = start.next → the node that will be moved to the front during reversal.
Perform (right - left) iterations:
Temporarily save then.next.
Remove then from its current place and insert it after pre.
Update start.next to bypass then.
Update then to the next node to be processed.
This is the standard "reverse a portion by continuously inserting next node at front of that portion".
Visualization:
Before: pre -> [start -> then -> ...]
After one iteration: pre -> [then -> start -> ...]
After repeating, the segment [left, right] is fully reversed.
Return dummy.next (in case head changed when left = 1).
Key Observations / Edge Cases:
When left == right: No change; method naturally does zero iterations.
When left == 1:
pre is dummy, so reversing starts at the head; dummy.next becomes new head.
Handles arbitrary values of node.val (they don’t affect the logic).
Only a single traversal over the list:
Move pre to left-1 → O(n) in worst case
Inner reversal loop also covered in same traversal segment.
Pseudo-code:
Complexity Analysis:
Time Complexity:
We traverse at most once over the list and reverse within that traversal.
Overall: O(n) where n is the number of nodes.
Space Complexity:
Only a few pointers used; no extra data structures proportional to n.
Overall: O(1) extra space.
5. Java code
6. C code
7. C++ code
8. Python code
9. JavaScript code
Comments
Post a Comment