92. Reverse Linked List II - Explanation
Description
You are 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 (1-indexed), and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5], left = 1, right = 3
Output: [3,2,1,4,5]Example 2:
Input: head = [1,1], left = 1, right = 1
Output: [1,1]Constraints:
- The number of nodes in the list is
n. 1 <= n <= 500.-500 <= Node.val <= 5001 <= left <= right <= n
Follow up: Could you do it in one pass?
Topics
Prerequisites
Before attempting this problem, you should be comfortable with:
- Reverse Linked List (Basic) - This problem builds on the standard linked list reversal technique
- Dummy Node Technique - Using a dummy node to simplify edge cases when the head might change
- Linked List Traversal - Navigating to specific positions in a linked list by counting nodes
- Pointer Manipulation - Carefully managing multiple pointers to disconnect, reverse, and reconnect list segments
1. Recursion - I
Intuition
To reverse a portion of a linked list, we first locate the sublist boundaries, disconnect it from the rest, reverse it using standard list reversal, and reconnect the pieces. A dummy node simplifies edge cases where the reversal starts at the head. The recursive reversal handles the sublist by making each node point to its predecessor.
Algorithm
- Create a dummy node pointing to the head to handle edge cases.
- Traverse to find the node just before position
left(call itprev). - Identify the sublist head
sublist_headand traverse to find the sublist tailsublist_tailat positionright. - Save the node after the sublist (
nextNode) and disconnect the sublist by settingsublist_tail.nexttonull. - Recursively reverse the sublist: base case returns the single node; otherwise, recurse on the next node and make it point back.
- Connect
prevto the new sublist head (returned from reversal) and connect the original sublist head (now tail) tonextNode. - Return
dummy.next.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
prev = dummy
for _ in range(left - 1):
prev = prev.next
sublist_head = prev.next
sublist_tail = sublist_head
for _ in range(right - left):
sublist_tail = sublist_tail.next
next_node = sublist_tail.next
sublist_tail.next = None
reversed_sublist = self.reverseList(sublist_head)
prev.next = reversed_sublist
sublist_head.next = next_node
return dummy.next
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
newHead = head
if head.next:
newHead = self.reverseList(head.next)
head.next.next = head
head.next = None
return newHeadTime & Space Complexity
- Time complexity:
- Space complexity: for recursion stack.
2. Recursion - II
Intuition
This approach uses recursion to navigate to the start of the reversal range. Once left equals 1, we reverse the first right nodes using a helper that tracks the successor node (the node after the reversed portion). The key insight is that as recursion unwinds, we can rewire pointers to achieve the reversal while maintaining the connection to the rest of the list.
Algorithm
- If
leftis 1, call the helper functionreverseListto reverse the firstrightnodes. - Otherwise, recurse with
head.nextand decrementedleftandrightvalues, then attach the result tohead.next. - The helper function
reverseListreversesnnodes starting from the given node:- Base case: when
nis 1, save thesuccessor(next node) and return current node. - Recurse on the next node with
n - 1. - After recursion, make the next node point back to current and set current's next to the saved
successor.
- Base case: when
- Return the new head of the reversed portion.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
def reverseList(node, n):
if n == 1:
return node, node.next
new_head, next_node = reverseList(node.next, n - 1)
node.next.next = node
node.next = next_node
return new_head, next_node
if left == 1:
new_head, _ = reverseList(head, right)
return new_head
head.next = self.reverseBetween(head.next, left - 1, right - 1)
return headTime & Space Complexity
- Time complexity:
- Space complexity: for recursion stack.
3. Iteration - I
Intuition
The iterative approach follows the same structure as the first recursive solution but reverses the sublist using a loop instead of recursion. We traverse to find the boundaries, detach the sublist, reverse it in place using the standard three-pointer technique, and reconnect everything.
Algorithm
- Create a dummy node pointing to the head.
- Traverse
left - 1steps to findprev(node before the sublist). - Identify the sublist head
sublist_headand traverseright - leftmore steps to find the sublist tailsublist_tail. - Save the node after the sublist
nextNodeand disconnect by settingsublist_tail.nexttonull. - Reverse the sublist iteratively using
prevandcurrpointers:- For each node, save next, point
currtoprev, advance both pointers.
- For each node, save next, point
- Connect
prev.nextto the new head (finalprevafter reversal) and connect the original head (now tail) to the saved successor. - Return
dummy.next.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
prev = dummy
for _ in range(left - 1):
prev = prev.next
sublist_head = prev.next
sublist_tail = sublist_head
for _ in range(right - left):
sublist_tail = sublist_tail.next
next_node = sublist_tail.next
sublist_tail.next = None
reversed_sublist = self.reverseList(sublist_head)
prev.next = reversed_sublist
sublist_head.next = next_node
return dummy.next
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev, curr = None, head
while curr:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
return prevTime & Space Complexity
- Time complexity:
- Space complexity: extra space.
4. Iteration - II
Intuition
This approach reverses in a single pass without explicitly detaching the sublist. After finding the node before the reversal starts, we reverse links one at a time as we traverse. The key is maintaining a reference to the original sublist head (which becomes the tail after reversal) so we can reconnect it to the node following the reversed section.
Algorithm
- Create a dummy node pointing to the head.
- Traverse
left - 1steps to positionleftPrev(node before reversal) andcur(first node to reverse). - Reverse
right - left + 1nodes in place:- Save
cur.nextastmpNext. - Point
cur.nexttoprev. - Advance
prevtocurandcurtotmpNext.
- Save
- After the loop,
prevpoints to the new head of the reversed section andcurpoints to the node after it. - Connect
leftPrev.next.next(original first node, now last) tocur. - Connect
leftPrev.nexttoprev(the new head). - Return
dummy.next.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
leftPrev, cur = dummy, head
for _ in range(left - 1):
leftPrev, cur = cur, cur.next
prev = None
for _ in range(right - left + 1):
tmpNext = cur.next
cur.next = prev
prev, cur = cur, tmpNext
leftPrev.next.next = cur
leftPrev.next = prev
return dummy.nextTime & Space Complexity
- Time complexity:
- Space complexity: extra space.
Common Pitfalls
Not Using a Dummy Node for Edge Cases
When left equals 1, the head of the list changes after reversal. Without a dummy node pointing to the head, you lose the reference to the new head and cannot return the correct result. The dummy node provides a stable anchor that simplifies edge case handling when the reversal starts at the beginning.
Forgetting to Reconnect the Reversed Sublist
After reversing the sublist, both ends must be reconnected to the rest of the list. A common mistake is connecting only one end, either forgetting to link the node before position left to the new sublist head, or forgetting to link the new sublist tail to the node after position right. Both connections are essential.
Incorrect Pointer Updates During In-Place Reversal
The single-pass reversal approach requires careful tracking of multiple pointers. A frequent error is updating leftPrev.next before using it to access the original sublist head. Since leftPrev.next initially points to the first node being reversed (which becomes the tail), you must save this reference or use it correctly before overwriting it with the new head.
Sign in to join the discussion