Reverse Linked List II

Difficulty: Medium
Topics: Linked List
Link: https://leetcode.com/problems/reverse-linked-list-ii/

Problem 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.

Example 1:


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

Example 2:


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

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?

Solution

1. Problem Deconstruction

Technical Restatement
Given a singly-linked list $L$ with $n$ nodes and integer indices $left$ and $right$ where $1 \leq left \leq right \leq n$ , reverse the sublist spanning positions $left$ through $right$ (1-indexed) while preserving all other nodes. Return the modified list head. The reversal must be in-place with $O(1)$ auxiliary space.

Beginner Explanation
Imagine a conga line where people hold shoulders. You’re told to reverse a section of the line (say people 2-4), while keeping others connected. The first person stays first, but people 2-4 now face backward, with person 4 becoming second, person 3 third, etc. After reversal, person 1 holds person 4’s shoulders, person 2 holds person 5’s shoulders.

Mathematical Formulation
Let $L = [v_1, v_2, ..., v_n]$ be node values. Define reversal operator $R(i,j)$ that transforms $L$ to:

[v_1, ..., v_{i-1}, v_j, v_{j-1}, ..., v_i, v_{j+1}, ..., v_n]

Constraints enforce:

$|L| = n \geq 1$
$1 \leq i \leq j \leq n$
$v_k \in \mathbb{Z}, |v_k| \leq 500$

Constraint Analysis

n ≤ 500: Permits $O(n^2)$ solutions but expects $O(n)$
Node values bounded: No overflow concerns
left = right: Single-node reversal trivial case
left = 1: Head modification required
right = n: Tail connection handling
Single node list: Direct return head

2. Intuition Scaffolding

Real-World Metaphor
Like reversing train cars in a yard: Find the cars before/after the target section, decouple the segment, reverse it using a switching track, then reconnect to original train.

Gaming Analogy
In RPG inventory management: Your item slots 2-4 need reordering. You remove items 2-4, reverse their order, then place them back while keeping other slots intact.

Math Analogy
Treat as permutation transformation: Original indices $(1,2,...,n)$ become $(1, j, j-1, ..., i, j+1, ..., n)$ through cyclic subgroup reversal.

Common Pitfalls

Off-by-one errors: 1-indexing vs 0-indexing confusion
Lost head reference: When left=1, new head isn’t returned
Broken connections: Failing to reconnect reversed segment’s tail
Single-node handling: Special casing left=right unnecessarily
Null pointer exceptions: Not checking node existence before access

3. Approach Encyclopedia

Brute Force - External Storage

def reverseBetween(head, left, right):
    values = []
    curr = head
    # Collect all values O(n)
    while curr:
        values.append(curr.val)
        curr = curr.next
    
    # Reverse subarray O(k) where k = right-left+1
    l, r = left-1, right-1
    while l < r:
        values[l], values[r] = values[r], values[l]
        l += 1
        r -= 1
    
    # Rebuild list O(n)
    dummy = ListNode(0)
    curr = dummy
    for val in values:
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next

Complexity: Time $O(3n) = O(n)$ , Space $O(n)$ for value storage + $O(n)$ new nodes = $O(n)$

Optimized - One Pass In-Place

Input: 1 → 2 → 3 → 4 → 5, left=2, right=4

Step 1: Find connection points
        prev
         ↓
dummy → 1 → 2 → 3 → 4 → 5

Step 2: Reverse segment iteratively
        prev   curr  next
         ↓      ↓     ↓
dummy → 1 → 2 → 3 → 4 → 5

First iteration: 2 → 1, 3 → 2, prev.next → 3
        prev         curr  next  
         ↓            ↓     ↓
dummy → 1 → 3 → 2 → 4 → 5

Second iteration: 3 → 4 → 2, prev.next → 4
        prev              curr next  
         ↓                 ↓    ↓
dummy → 1 → 4 → 3 → 2 → 5

4. Code Deep Dive

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def reverseBetween(head, left, right):
    # Edge case: single node or no reversal needed
    if not head or left == right:
        return head
    
    # Dummy node handles left=1 case uniformly
    dummy = ListNode(0, head)  # What: Sentinel node
    prev = dummy               # Why: Track node before reversal segment
    
    # Move prev to node before reversal start (position left-1)
    for _ in range(left - 1):  # How: Advance left-1 times
        prev = prev.next
    
    # Reverse the sublist
    curr = prev.next           # Start of reversal segment
    for _ in range(right - left):  # How: Perform k-1 reversals
        next_node = curr.next       # Cache next node
        curr.next = next_node.next  # Bypass next_node
        next_node.next = prev.next  # Insert at front of segment
        prev.next = next_node       # Update segment head
    
    return dummy.next  # Handles head modification case

Edge Case Handling

Example 1: When left=2, prev lands at node1. Reversal correctly connects 1→4→3→2→5
Example 2: left=right=1, immediate return preserves single node
left=1: dummy ensures new head (4) is returned via dummy.next
right=n: curr.next becomes None naturally at list end

5. Complexity War Room

Hardware-Aware Analysis
At n=500, the algorithm uses ~4KB memory (8 bytes/pointer × 500 nodes), fitting comfortably in L1 cache. Pointer chasing exhibits predictable access patterns favorable for CPU prefetching.

Approach Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n)	O(n)	10/10	❌ Violates in-place requirement
Stack Reversal	O(n)	O(k)	8/10	⚠️ Uses O(k) extra space
One-Pass In-Place	O(n)	O(1)	7/10	✅ Optimal

6. Pro Mode Extras

Variants Section

Reverse in Groups of K: Modify to reverse every k nodes (LC 25)
Reverse Entire List: Special case left=1, right=n (LC 206)
Multiple Intervals: Support multiple [left,right] reversal pairs
Doubly Linked List: Simplified with prev pointers

Interview Cheat Sheet

First Mention: “This is a linked list modification problem requiring O(1) space”
Critical Insight: “Dummy node elegantly handles head modification edge cases”
Whiteboard Strategy: Draw initial state, show 2-3 reversal steps, then final connections
Testing Checklist: left=1, right=n, single node, two-node list, left=right
Optimization Path: “From O(n) space value storage → O(k) stack → O(1) in-place”

#92 - Reverse Linked List II