title: Reverse Linked List II
slug: reverse-linked-list-ii
difficulty: medium
leetcode_id: 92
leetcode_url: https://leetcode.com/problems/reverse-linked-list-ii/
categories:
  - linked-lists
patterns:
  - slug: linkedlist-reversal
    is_optimal: true

function_signature: "def reverse_between(head: ListNode, left: int, right: int) -> ListNode:"

test_cases:
  visible:
    - input: { head: [1, 2, 3, 4, 5], left: 2, right: 4 }
      expected: [1, 4, 3, 2, 5]
    - input: { head: [5], left: 1, right: 1 }
      expected: [5]
  hidden:
    - input: { head: [1, 2, 3], left: 1, right: 3 }
      expected: [3, 2, 1]
    - input: { head: [1, 2, 3], left: 1, right: 2 }
      expected: [2, 1, 3]
    - input: { head: [1, 2, 3], left: 2, right: 3 }
      expected: [1, 3, 2]
    - input: { head: [1, 2], left: 1, right: 2 }
      expected: [2, 1]
    - input: { head: [1, 2, 3, 4, 5], left: 1, right: 5 }
      expected: [5, 4, 3, 2, 1]

description: |
  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*.

  **Note:** Positions are 1-indexed.

constraints: |
  - The number of nodes in the list is `n`
  - `1 <= n <= 500`
  - `-500 <= Node.val <= 500`
  - `1 <= left <= right <= n`

examples:
  - input: "head = [1,2,3,4,5], left = 2, right = 4"
    output: "[1,4,3,2,5]"
    explanation: "Nodes at positions 2, 3, and 4 (values 2, 3, 4) are reversed to become 4, 3, 2. The list becomes 1→4→3→2→5."
  - input: "head = [5], left = 1, right = 1"
    output: "[5]"
    explanation: "A single node reversed is just itself."

explanation:
  intuition: |
    Imagine you have a chain of paper clips where you want to reverse only a *section* in the middle, leaving the rest unchanged.

    The key insight is to break the problem into parts:
    1. **Navigate** to the node just before the reversal starts (position `left - 1`)
    2. **Reverse** the sublist from position `left` to `right` (using the same technique from "Reverse Linked List")
    3. **Reconnect** the reversed section back into the original list

    Think of it like this: if you have `1 → 2 → 3 → 4 → 5` and want to reverse positions 2-4, you're essentially:
    - Disconnecting the segment `2 → 3 → 4`
    - Reversing it to `4 → 3 → 2`
    - Reconnecting: node `1` now points to `4`, and node `2` now points to `5`

    The tricky part is keeping track of the right nodes to reconnect. Using a **dummy node** before the head simplifies edge cases when `left = 1` (reversing from the beginning).

  approach: |
    We solve this using a **Single Pass with Dummy Node** approach:

    **Step 1: Create a dummy node**

    - `dummy.next = head`: This handles the edge case where `left = 1` gracefully
    - `prev = dummy`: Start `prev` at the dummy so after `left - 1` moves, it's right before the reversal zone

    &nbsp;

    **Step 2: Move prev to the node before position left**

    - Move `prev` forward `left - 1` times
    - After this, `prev` points to the node just before where reversal begins
    - `curr = prev.next`: This is the first node to be reversed (will become the tail of the reversed section)

    &nbsp;

    **Step 3: Reverse the sublist using pointer manipulation**

    - We perform `right - left` reversal operations
    - For each operation:
      - `next_node = curr.next`: The node we're moving to the front
      - `curr.next = next_node.next`: Skip over `next_node`
      - `next_node.next = prev.next`: Insert `next_node` at the front of the reversed section
      - `prev.next = next_node`: Update `prev` to point to the new front

    &nbsp;

    **Step 4: Return the new head**

    - Return `dummy.next` (the dummy node handles the case where the head itself was reversed)

    &nbsp;

    This elegant approach reverses the section in-place without needing to first disconnect it.

  common_pitfalls:
    - title: Not Using a Dummy Node
      description: |
        When `left = 1`, the head of the list changes. Without a dummy node, you need special-case handling:

        ```python
        # Without dummy: messy edge case handling
        if left == 1:
            # Special logic for when head changes
            ...
        ```

        A dummy node before the head means `prev` always has a valid node to work with, and `dummy.next` always points to the (possibly new) head.
      wrong_approach: "Special-casing when left = 1"
      correct_approach: "Use dummy node so prev.next always works"

    - title: Off-by-One Errors in Counting
      description: |
        The problem uses **1-indexed** positions, but we iterate starting from index 0 in code.

        - To reach the node *before* position `left`, move `prev` forward `left - 1` times
        - To reverse nodes from `left` to `right`, perform `right - left` reversal operations

        Trace through a small example: for `left = 2, right = 4`, we need to reverse 3 nodes, which requires `4 - 2 = 2` "move to front" operations.
      wrong_approach: "Moving left times or reversing right - left + 1 times"
      correct_approach: "Move left - 1 times, reverse right - left times"

    - title: Losing Track of the Tail of Reversed Section
      description: |
        The node at position `left` (stored in `curr`) becomes the **tail** of the reversed section after all operations.

        A common mistake is moving `curr` during the reversal. But `curr` should stay fixed — it's the anchor that will eventually connect to the node after position `right`.

        The reversal works by repeatedly taking `curr.next` and moving it to the front, while `curr` stays in place (but its `next` pointer keeps changing).
      wrong_approach: "Moving curr during reversal operations"
      correct_approach: "Keep curr fixed; it moves nodes in front of itself"

  key_takeaways:
    - "**Dummy node pattern**: When the head might change, a dummy node before head simplifies the logic and eliminates edge cases"
    - "**In-place reversal**: We don't need extra space for a temporary list — pointer manipulation reverses the section in-place"
    - "**Building on fundamentals**: This problem combines 'navigate to position' with 'reverse linked list' — mastering the basic reversal makes this approachable"
    - "**Follow-up achieved**: The single-pass approach processes each node at most once, achieving O(n) time"

  time_complexity: "O(n). We traverse at most n nodes: `left - 1` to reach the start, then `right - left` reversal operations, totalling at most n steps."
  space_complexity: "O(1). We only use a constant number of pointer variables (`dummy`, `prev`, `curr`, `next_node`), regardless of list size."

solutions:
  - approach_name: Single Pass with Dummy Node
    is_optimal: true
    code: |
      class ListNode:
          def __init__(self, val=0, next=None):
              self.val = val
              self.next = next

      def reverse_between(head: ListNode | None, left: int, right: int) -> ListNode | None:
          if not head or left == right:
              return head  # Nothing to reverse

          # Dummy node handles edge case when left = 1
          dummy = ListNode(0, head)
          prev = dummy

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

          # curr is the first node in the reversal zone
          # It will become the tail of the reversed section
          curr = prev.next

          # Reverse by moving nodes one by one to the front
          for _ in range(right - left):
              # next_node is the node we're moving to the front
              next_node = curr.next

              # Remove next_node from its current position
              curr.next = next_node.next

              # Insert next_node at the front of the reversed section
              next_node.next = prev.next
              prev.next = next_node

          return dummy.next
    explanation: |
      **Time Complexity:** O(n) — Single pass through the list.

      **Space Complexity:** O(1) — Only pointer variables used.

      The key insight is that we don't physically disconnect and reconnect the sublist. Instead, we repeatedly take the node after `curr` and move it to the front of the reversed section. After `right - left` such operations, the sublist is reversed in place.

  - approach_name: Two Pass (Extract and Reverse)
    is_optimal: false
    code: |
      def reverse_between(head: ListNode | None, left: int, right: int) -> ListNode | None:
          if not head or left == right:
              return head

          dummy = ListNode(0, head)

          # First pass: find the boundaries
          before_left = dummy
          for _ in range(left - 1):
              before_left = before_left.next

          # Mark the start and end of reversal section
          rev_start = before_left.next

          rev_end = before_left
          for _ in range(right - left + 1):
              rev_end = rev_end.next

          after_right = rev_end.next

          # Reverse the section using standard reversal
          prev = after_right  # New tail points to node after section
          curr = rev_start

          while curr != after_right:
              next_node = curr.next
              curr.next = prev
              prev = curr
              curr = next_node

          # Reconnect: before_left now points to rev_end (new front)
          before_left.next = prev

          return dummy.next
    explanation: |
      **Time Complexity:** O(n) — Two passes through part of the list.

      **Space Complexity:** O(1) — Only pointer variables used.

      This approach is more intuitive: first locate the boundaries, then apply the standard linked list reversal to that section. While still O(n), it requires more traversal than the single-pass approach. Useful for understanding, but the single-pass solution is more elegant.
