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.

Examples

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

1 → [2 → 3 → 4] → 5
      ↓ reverse ↓
1 → [4 → 3 → 2] → 5

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

Constraints

  • 1 <= n <= 500 (number of nodes)
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

Thinking Process

Break It Into 3 Parts

  1. Traverse to the node before left – call it prev
  2. Reverse the sublist [left .. right]
  3. Reconnect: prev → new head of reversed sublist, tail of reversed sublist → node after right

The Head Insertion Trick

Instead of doing a standard three-pointer reversal and then reconnecting, we can use head insertion: repeatedly pull the node after curr to the front of the sublist. This avoids re-traversing and naturally keeps all connections intact.

Initial:  prev → [a → b → c → d] → next
                  ↑             ↑
                left          right

Step 1: move b before a
          prev → [b → a → c → d] → next

Step 2: move c before b
          prev → [c → b → a → d] → next

Step 3: move d before c
          prev → [d → c → b → a] → next

Each step does 3 pointer swaps and the sublist grows by one node at the front.

Edge Cases

Case Handling
left == 1 (head changes) Dummy node absorbs head change
left == right (no-op) Early return
Single node Early return
Linked list: pointer walk 1 2 3 slow → → fast (2x speed)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Iterative pointer walk (this problem) O(n) O(1) Traversal, insertion
Dummy head node O(n) O(1) Simplify head-edge cases
Reversal (3-pointer) O(n) O(1) Reverse sublist or full list
Slow/fast pointers O(n) O(1) Middle, cycle, merge lists

Solution

from typing import Optional


# 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"]:
        if not head or left == right:
            return head

        dummy = ListNode(0, head)
        prev = dummy

        # Move prev to node before 'left'.
        for _ in range(left - 1):
            prev = prev.next

        # Reverse sublist using head insertion.
        curr = prev.next
        for _ in range(right - left):
            nxt = curr.next
            curr.next = nxt.next
            nxt.next = prev.next
            prev.next = nxt

        return dummy.next

Solution Explanation

Approach: Iterative pointer walk (this problem)

Key idea: ### Break It Into 3 Parts

How the code works:

  1. Traverse to the node before left – call it prev
  2. Reverse the sublist [left .. right]
  3. Reconnect: prev → new head of reversed sublist, tail of reversed sublist → node after right

Walkthrough — input head = [1,2,3,4,5], left = 2, right = 4, expected output [1,4,3,2,5]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Comparison

Aspect Head Insertion Classic Reversal
Uses dummy node Yes (handles left == 1) No (explicit if for left == 1)
curr pointer movement Stays fixed Advances through sublist
Reconnection Automatic (pointers stay connected) Manual (set con.next and tail.next)
Conceptual complexity Lower – single pattern repeated Higher – two distinct phases

Common Mistakes

  • Off-by-one on prev: Walking left steps from dummy lands on node left, but we need node left - 1. Walk left - 1 steps instead.
  • Moving curr in head insertion: curr should stay fixed – it’s always the tail of the growing reversed sublist. Only tmp moves.
  • Forgetting left == 1: Without a dummy, the head of the list changes. Either use a dummy or handle this case explicitly.

Key Takeaways

  • Head insertion is the cleanest pattern for partial reversal – no separate reconnection step needed
  • A dummy node eliminates the left == 1 edge case entirely
  • Both approaches are O(n) time and O(1) space – the choice is about clarity, not performance

References

Template Reference