92. Reverse Linked List II - Explanation

Problem Link

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 <= 500
• 1 <= left <= right <= n

Follow up: Could you do it in one pass?

Company Tags

Please upgrade to NeetCode Pro to view company tags.

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

1. Create a dummy node pointing to the head to handle edge cases.
2. Traverse to find the node just before position left (call it prev).
3. Identify the sublist head sublist_head and traverse to find the sublist tail sublist_tail at position right.
4. Save the node after the sublist (nextNode) and disconnect the sublist by setting sublist_tail.next to null.
5. Recursively reverse the sublist: base case returns the single node; otherwise, recurse on the next node and make it point back.
6. Connect prev to the new sublist head (returned from reversal) and connect the original sublist head (now tail) to nextNode.
7. 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 newHead

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$ 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

1. If left is 1, call the helper function reverseList to reverse the first right nodes.
2. Otherwise, recurse with head.next and decremented left and right values, then attach the result to head.next.
3. The helper function reverseList reverses n nodes starting from the given node:
   • Base case: when n is 1, save the successor (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.
4. 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 head

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$ 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

1. Create a dummy node pointing to the head.
2. Traverse left - 1 steps to find prev (node before the sublist).
3. Identify the sublist head sublist_head and traverse right - left more steps to find the sublist tail sublist_tail.
4. Save the node after the sublist nextNode and disconnect by setting sublist_tail.next to null.
5. Reverse the sublist iteratively using prev and curr pointers:
   • For each node, save next, point curr to prev, advance both pointers.
6. Connect prev.next to the new head (final prev after reversal) and connect the original head (now tail) to the saved successor.
7. 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 prev

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ 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

1. Create a dummy node pointing to the head.
2. Traverse left - 1 steps to position leftPrev (node before reversal) and cur (first node to reverse).
3. Reverse right - left + 1 nodes in place:
   • Save cur.next as tmpNext.
   • Point cur.next to prev.
   • Advance prev to cur and cur to tmpNext.
4. After the loop, prev points to the new head of the reversed section and cur points to the node after it.
5. Connect leftPrev.next.next (original first node, now last) to cur.
6. Connect leftPrev.next to prev (the new head).
7. 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.next

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ 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.