Reverse Linked List II

Problem Statement

Given the head of a 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.

What to notice first

• Positions are 1-indexed (not 0-indexed), so position 1 is the head node.
• Only the sublist from position left to right is reversed; the rest stays in place.
• The reversal must be done in-place — do not allocate new nodes.
• A dummy node simplifies handling the case where reversal starts at the head.

Examples

Input	left	right	Output	Explanation
1→2→3→4→5→null	2	4	1→4→3→2→5→null	Reverse nodes 2, 3, 4
5→null	1	1	5→null	Single node, no reversal needed
1→2→null	1	2	2→1→null	Reverse the entire list

Constraints

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Real-World Applications

Where this pattern appears

• Log rotation — reverse a section of log entries in a linked structure.
• Undo/redo stacks — partially reverse command history from position m to n.
• Playlist reordering — reverse a range of songs in a linked playlist structure.
• Data stream chunking — reverse a window of elements in streaming linked data.

Complexity Comparison

Approach	Time	Space	Best When
Iterative (Pointers)	O(n)	O(1)	Interview favorite; intuitive pointer manipulation
Recursive	O(n)	O(n)	More elegant; stack tracks position

Which approach should you learn first?

• Learn Iterative with Pointers first — it is the most common interview approach and demonstrates pointer mastery.
• Understand Recursive as a bonus — it showcases elegant backtracking and position tracking.

Interview Favorite

Iterative with Pointers

O(n) time · O(1) space

Elegant & Recursive

Recursive

O(n) time · O(n) space

Approach 1: Iterative with Pointers

★ Recommended

Use a dummy node pointing to the head to simplify edge cases. Advance to position left - 1 (the node before the reversal). Then, perform right - left reversals by moving nodes to the front of the sublist.

⏱ Time O(n) Single pass through list 💾 Space O(1) Pointer variables only

Step-by-step Example

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

Step	Action	List State
Create dummy	Dummy points to 1	dummy→1→2→3→4→5→null
Advance prev to node 1	Move left-1 times	prev=1, curr=2
Reverse 1→2→4	Move 2 in front	1→3→2→4→5→null
Reverse 1→3→4	Move 3 in front	1→4→3→2→5→null
Connect tail	Ensure 2→5	1→4→3→2→5→null ✓

Animated walkthrough

How iterative pointer reversal works step-by-step

Use Next or Autoplay to see the dummy node, pointer positioning, and the reversal loop in action.

Back Autoplay Next Reset

Step 1 of 4

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function reverseBetween(head, left, right):
    if left == right:
        return head

    dummy = ListNode(0, head)
    prev = dummy

    # Advance prev to position left-1
    for i in range(left - 1):
        prev = prev.next

    curr = prev.next

    # Reverse right - left times
    for i in range(right - left):
        next_temp = curr.next
        curr.next = next_temp.next
        next_temp.next = prev.next
        prev.next = next_temp

    return dummy.next

Solution Code

Python

reverse_linked_list_ii_iterative.py

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverseBetween(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    """
    Reverse a portion of a linked list from position left to right (1-indexed).

    Time Complexity: O(n) - single pass through the list
    Space Complexity: O(1) - only pointer variables

    Strategy:
    1. Create a dummy node to handle edge case of reversing from head
    2. Advance prev pointer to position left-1
    3. Perform (right - left) reversals by moving nodes to the front of the sublist
    4. Return dummy.next
    """
    if left == right:
        return head

    # Create dummy node pointing to head
    dummy = ListNode(0, head)
    prev = dummy

    # Advance prev to position left-1
    for _ in range(left - 1):
        prev = prev.next

    # curr is the first node to reverse (at position left)
    curr = prev.next

    # Perform (right - left) reversals
    for _ in range(right - left):
        # next_temp is the node we want to move to the front
        next_temp = curr.next
        # Bypass next_temp by connecting curr to next_temp.next
        curr.next = next_temp.next
        # Move next_temp to the front of the sublist
        next_temp.next = prev.next
        prev.next = next_temp

    return dummy.next


# Test cases
def list_to_array(head: Optional[ListNode]) -> list:
    """Convert linked list to array for easy comparison."""
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result


def array_to_list(arr: list) -> Optional[ListNode]:
    """Convert array to linked list."""
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


# Test 1: Reverse middle portion
head1 = array_to_list([1, 2, 3, 4, 5])
result1 = reverseBetween(head1, 2, 4)
print(list_to_array(result1))  # [1, 4, 3, 2, 5]

# Test 2: Single node (no reversal)
head2 = array_to_list([5])
result2 = reverseBetween(head2, 1, 1)
print(list_to_array(result2))  # [5]

# Test 3: Reverse entire list
head3 = array_to_list([1, 2])
result3 = reverseBetween(head3, 1, 2)
print(list_to_array(result3))  # [2, 1]

# Test 4: Reverse from start
head4 = array_to_list([1, 2, 3, 4, 5])
result4 = reverseBetween(head4, 1, 3)
print(list_to_array(result4))  # [3, 2, 1, 4, 5]

# Test 5: Reverse at end
head5 = array_to_list([1, 2, 3, 4, 5])
result5 = reverseBetween(head5, 3, 5)
print(list_to_array(result5))  # [1, 2, 5, 4, 3]

C++

reverse_linked_list_ii_iterative.cpp

#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

/**
 * Reverse a portion of a linked list from position left to right (1-indexed).
 *
 * Time Complexity: O(n) - single pass through the list
 * Space Complexity: O(1) - only pointer variables
 *
 * Strategy:
 * 1. Create a dummy node to handle edge case of reversing from head
 * 2. Advance prev pointer to position left-1
 * 3. Perform (right - left) reversals by moving nodes to the front of the sublist
 * 4. Return dummy->next
 */
ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (left == right) {
        return head;
    }

    // Create dummy node pointing to head
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* prev = dummy;

    // Advance prev to position left-1
    for (int i = 0; i < left - 1; i++) {
        prev = prev->next;
    }

    // curr is the first node to reverse (at position left)
    ListNode* curr = prev->next;

    // Perform (right - left) reversals
    for (int i = 0; i < right - left; i++) {
        // next_temp is the node we want to move to the front
        ListNode* next_temp = curr->next;
        // Bypass next_temp by connecting curr to next_temp->next
        curr->next = next_temp->next;
        // Move next_temp to the front of the sublist
        next_temp->next = prev->next;
        prev->next = next_temp;
    }

    ListNode* result = dummy->next;
    delete dummy;
    return result;
}

// Helper function to create a linked list from a vector
ListNode* createList(const vector<int>& values) {
    if (values.empty()) return nullptr;
    ListNode* head = new ListNode(values[0]);
    ListNode* current = head;
    for (int i = 1; i < values.size(); i++) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    return head;
}

// Helper function to print a linked list
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << "\n";
}

// Helper function to delete a linked list
void deleteList(ListNode* head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

// Test cases
int main() {
    // Test 1: Reverse middle portion
    ListNode* head1 = createList({1, 2, 3, 4, 5});
    ListNode* result1 = reverseBetween(head1, 2, 4);
    cout << "Test 1: ";
    printList(result1);  // 1 4 3 2 5
    deleteList(result1);

    // Test 2: Single node (no reversal)
    ListNode* head2 = createList({5});
    ListNode* result2 = reverseBetween(head2, 1, 1);
    cout << "Test 2: ";
    printList(result2);  // 5
    deleteList(result2);

    // Test 3: Reverse entire list
    ListNode* head3 = createList({1, 2});
    ListNode* result3 = reverseBetween(head3, 1, 2);
    cout << "Test 3: ";
    printList(result3);  // 2 1
    deleteList(result3);

    // Test 4: Reverse from start
    ListNode* head4 = createList({1, 2, 3, 4, 5});
    ListNode* result4 = reverseBetween(head4, 1, 3);
    cout << "Test 4: ";
    printList(result4);  // 3 2 1 4 5
    deleteList(result4);

    // Test 5: Reverse at end
    ListNode* head5 = createList({1, 2, 3, 4, 5});
    ListNode* result5 = reverseBetween(head5, 3, 5);
    cout << "Test 5: ";
    printList(result5);  // 1 2 5 4 3
    deleteList(result5);

    return 0;
}

Java

reverse_linked_list_ii_iterative.java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Reverse a portion of a linked list from position left to right (1-indexed).
 *
 * Time Complexity: O(n) - single pass through the list
 * Space Complexity: O(1) - only pointer variables
 *
 * Strategy:
 * 1. Create a dummy node to handle edge case of reversing from head
 * 2. Advance prev pointer to position left-1
 * 3. Perform (right - left) reversals by moving nodes to the front of the sublist
 * 4. Return dummy.next
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) {
            return head;
        }

        // Create dummy node pointing to head
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;

        // Advance prev to position left-1
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }

        // curr is the first node to reverse (at position left)
        ListNode curr = prev.next;

        // Perform (right - left) reversals
        for (int i = 0; i < right - left; i++) {
            // nextTemp is the node we want to move to the front
            ListNode nextTemp = curr.next;
            // Bypass nextTemp by connecting curr to nextTemp.next
            curr.next = nextTemp.next;
            // Move nextTemp to the front of the sublist
            nextTemp.next = prev.next;
            prev.next = nextTemp;
        }

        return dummy.next;
    }
}

// Test harness
public class reverse_linked_list_ii_iterative {
    // Helper function to create a linked list from an array
    static ListNode createList(int[] values) {
        if (values.length == 0) return null;
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    // Helper function to convert linked list to array for comparison
    static List<Integer> listToArray(ListNode head) {
        List<Integer> result = new ArrayList<>();
        while (head != null) {
            result.add(head.val);
            head = head.next;
        }
        return result;
    }

    // Helper function to print a linked list
    static void printList(ListNode head) {
        List<Integer> values = listToArray(head);
        System.out.println(values);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // Test 1: Reverse middle portion
        ListNode head1 = createList(new int[]{1, 2, 3, 4, 5});
        ListNode result1 = solution.reverseBetween(head1, 2, 4);
        System.out.print("Test 1: ");
        printList(result1);  // [1, 4, 3, 2, 5]

        // Test 2: Single node (no reversal)
        ListNode head2 = createList(new int[]{5});
        ListNode result2 = solution.reverseBetween(head2, 1, 1);
        System.out.print("Test 2: ");
        printList(result2);  // [5]

        // Test 3: Reverse entire list
        ListNode head3 = createList(new int[]{1, 2});
        ListNode result3 = solution.reverseBetween(head3, 1, 2);
        System.out.print("Test 3: ");
        printList(result3);  // [2, 1]

        // Test 4: Reverse from start
        ListNode head4 = createList(new int[]{1, 2, 3, 4, 5});
        ListNode result4 = solution.reverseBetween(head4, 1, 3);
        System.out.print("Test 4: ");
        printList(result4);  // [3, 2, 1, 4, 5]

        // Test 5: Reverse at end
        ListNode head5 = createList(new int[]{1, 2, 3, 4, 5});
        ListNode result5 = solution.reverseBetween(head5, 3, 5);
        System.out.print("Test 5: ");
        printList(result5);  // [1, 2, 5, 4, 3]
    }
}

JavaScript

reverse_linked_list_ii_iterative.js

/**
 * Definition for singly-linked list node
 */
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Reverse a portion of a linked list from position left to right (1-indexed).
 *
 * Time Complexity: O(n) - single pass through the list
 * Space Complexity: O(1) - only pointer variables
 *
 * Strategy:
 * 1. Create a dummy node to handle edge case of reversing from head
 * 2. Advance prev pointer to position left-1
 * 3. Perform (right - left) reversals by moving nodes to the front of the sublist
 * 4. Return dummy.next
 *
 * @param {ListNode} head - The head of the linked list
 * @param {number} left - Starting position (1-indexed)
 * @param {number} right - Ending position (1-indexed)
 * @return {ListNode} - The head of the modified list
 */
function reverseBetween(head, left, right) {
    if (left === right) {
        return head;
    }

    // Create dummy node pointing to head
    const dummy = new ListNode(0, head);
    let prev = dummy;

    // Advance prev to position left-1
    for (let i = 0; i < left - 1; i++) {
        prev = prev.next;
    }

    // curr is the first node to reverse (at position left)
    let curr = prev.next;

    // Perform (right - left) reversals
    for (let i = 0; i < right - left; i++) {
        // nextTemp is the node we want to move to the front
        const nextTemp = curr.next;
        // Bypass nextTemp by connecting curr to nextTemp.next
        curr.next = nextTemp.next;
        // Move nextTemp to the front of the sublist
        nextTemp.next = prev.next;
        prev.next = nextTemp;
    }

    return dummy.next;
}

// Helper function to create a linked list from an array
function createList(values) {
    if (values.length === 0) return null;
    const head = new ListNode(values[0]);
    let current = head;
    for (let i = 1; i < values.length; i++) {
        current.next = new ListNode(values[i]);
        current = current.next;
    }
    return head;
}

// Helper function to convert linked list to array for comparison
function listToArray(head) {
    const result = [];
    while (head !== null) {
        result.push(head.val);
        head = head.next;
    }
    return result;
}

// Test cases
// Test 1: Reverse middle portion
const head1 = createList([1, 2, 3, 4, 5]);
const result1 = reverseBetween(head1, 2, 4);
console.log('Test 1:', listToArray(result1));  // [1, 4, 3, 2, 5]

// Test 2: Single node (no reversal)
const head2 = createList([5]);
const result2 = reverseBetween(head2, 1, 1);
console.log('Test 2:', listToArray(result2));  // [5]

// Test 3: Reverse entire list
const head3 = createList([1, 2]);
const result3 = reverseBetween(head3, 1, 2);
console.log('Test 3:', listToArray(result3));  // [2, 1]

// Test 4: Reverse from start
const head4 = createList([1, 2, 3, 4, 5]);
const result4 = reverseBetween(head4, 1, 3);
console.log('Test 4:', listToArray(result4));  // [3, 2, 1, 4, 5]

// Test 5: Reverse at end
const head5 = createList([1, 2, 3, 4, 5]);
const result5 = reverseBetween(head5, 3, 5);
console.log('Test 5:', listToArray(result5));  // [1, 2, 5, 4, 3]

module.exports = reverseBetween;

Rust

reverse_linked_list_ii_iterative.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

/**
 * Reverse a portion of a linked list from position left to right (1-indexed).
 *
 * Time Complexity: O(n) - single pass through the list
 * Space Complexity: O(1) - only pointer variables
 *
 * Strategy:
 * 1. Create a dummy node to handle edge case of reversing from head
 * 2. Advance prev pointer to position left-1
 * 3. Perform (right - left) reversals by moving nodes to the front of the sublist
 * 4. Return dummy.next
 */
pub fn reverse_between(
    head: Option<Rc<RefCell<ListNode>>>,
    left: i32,
    right: i32,
) -> Option<Rc<RefCell<ListNode>>> {
    if left == right {
        return head;
    }

    // Create dummy node pointing to head
    let mut dummy = Rc::new(RefCell::new(ListNode::new(0)));
    dummy.borrow_mut().next = head;

    let mut prev = dummy.clone();

    // Advance prev to position left-1
    for _ in 0..left - 1 {
        let next_node = prev.borrow_mut().next.take();
        if let Some(next) = next_node {
            prev = next;
        }
    }

    // curr is the first node to reverse (at position left)
    if let Some(curr_node) = prev.borrow_mut().next.take() {
        let mut curr = curr_node;

        // Perform (right - left) reversals
        for _ in 0..right - left {
            // Get the node we want to move to the front
            if let Some(next_temp) = curr.borrow_mut().next.take() {
                // curr.next = next_temp.next
                curr.borrow_mut().next = next_temp.borrow_mut().next.take();

                // Move next_temp to the front of the sublist
                next_temp.borrow_mut().next = prev.borrow_mut().next.take();
                prev.borrow_mut().next = Some(next_temp);
            }
        }

        // Restore curr to prev.next
        prev.borrow_mut().next = Some(curr);
    }

    dummy.borrow_mut().next.take()
}

// Helper function to create a linked list from a vector
fn create_list(values: Vec<i32>) -> Option<Rc<RefCell<ListNode>>> {
    if values.is_empty() {
        return None;
    }

    let mut head = Rc::new(RefCell::new(ListNode::new(values[0])));
    let mut current = head.clone();

    for val in &values[1..] {
        let new_node = Rc::new(RefCell::new(ListNode::new(*val)));
        current.borrow_mut().next = Some(new_node.clone());
        current = new_node;
    }

    Some(head)
}

// Helper function to convert linked list to vector
fn list_to_vec(head: Option<Rc<RefCell<ListNode>>>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut current = head;

    while let Some(node) = current {
        result.push(node.borrow().val);
        current = node.borrow_mut().next.take();
    }

    result
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_reverse_middle_portion() {
        let head = create_list(vec![1, 2, 3, 4, 5]);
        let result = reverse_between(head, 2, 4);
        assert_eq!(list_to_vec(result), vec![1, 4, 3, 2, 5]);
    }

    #[test]
    fn test_single_node() {
        let head = create_list(vec![5]);
        let result = reverse_between(head, 1, 1);
        assert_eq!(list_to_vec(result), vec![5]);
    }

    #[test]
    fn test_reverse_entire_list() {
        let head = create_list(vec![1, 2]);
        let result = reverse_between(head, 1, 2);
        assert_eq!(list_to_vec(result), vec![2, 1]);
    }

    #[test]
    fn test_reverse_from_start() {
        let head = create_list(vec![1, 2, 3, 4, 5]);
        let result = reverse_between(head, 1, 3);
        assert_eq!(list_to_vec(result), vec![3, 2, 1, 4, 5]);
    }

    #[test]
    fn test_reverse_at_end() {
        let head = create_list(vec![1, 2, 3, 4, 5]);
        let result = reverse_between(head, 3, 5);
        assert_eq!(list_to_vec(result), vec![1, 2, 5, 4, 3]);
    }
}

fn main() {
    // Test 1: Reverse middle portion
    let head1 = create_list(vec![1, 2, 3, 4, 5]);
    let result1 = reverse_between(head1, 2, 4);
    println!("Test 1: {:?}", list_to_vec(result1));  // [1, 4, 3, 2, 5]

    // Test 2: Single node (no reversal)
    let head2 = create_list(vec![5]);
    let result2 = reverse_between(head2, 1, 1);
    println!("Test 2: {:?}", list_to_vec(result2));  // [5]

    // Test 3: Reverse entire list
    let head3 = create_list(vec![1, 2]);
    let result3 = reverse_between(head3, 1, 2);
    println!("Test 3: {:?}", list_to_vec(result3));  // [2, 1]

    // Test 4: Reverse from start
    let head4 = create_list(vec![1, 2, 3, 4, 5]);
    let result4 = reverse_between(head4, 1, 3);
    println!("Test 4: {:?}", list_to_vec(result4));  // [3, 2, 1, 4, 5]

    // Test 5: Reverse at end
    let head5 = create_list(vec![1, 2, 3, 4, 5]);
    let result5 = reverse_between(head5, 3, 5);
    println!("Test 5: {:?}", list_to_vec(result5));  // [1, 2, 5, 4, 3]
}

Go

reverse_linked_list_ii_iterative.go

package main

import "fmt"

type ListNode struct {
  Val  int
  Next *ListNode
}

/**
 * Reverse a portion of a linked list from position left to right (1-indexed).
 *
 * Time Complexity: O(n) - single pass through the list
 * Space Complexity: O(1) - only pointer variables
 *
 * Strategy:
 * 1. Create a dummy node to handle edge case of reversing from head
 * 2. Advance prev pointer to position left-1
 * 3. Perform (right - left) reversals by moving nodes to the front of the sublist
 * 4. Return dummy.Next
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
  if left == right {
    return head
  }

  // Create dummy node pointing to head
  dummy := &ListNode{Val: 0, Next: head}
  prev := dummy

  // Advance prev to position left-1
  for i := 0; i < left-1; i++ {
    prev = prev.Next
  }

  // curr is the first node to reverse (at position left)
  curr := prev.Next

  // Perform (right - left) reversals
  for i := 0; i < right-left; i++ {
    // nextTemp is the node we want to move to the front
    nextTemp := curr.Next
    // Bypass nextTemp by connecting curr to nextTemp.Next
    curr.Next = nextTemp.Next
    // Move nextTemp to the front of the sublist
    nextTemp.Next = prev.Next
    prev.Next = nextTemp
  }

  return dummy.Next
}

// Helper function to create a linked list from a slice
func createList(values []int) *ListNode {
  if len(values) == 0 {
    return nil
  }
  head := &ListNode{Val: values[0]}
  current := head
  for i := 1; i < len(values); i++ {
    current.Next = &ListNode{Val: values[i]}
    current = current.Next
  }
  return head
}

// Helper function to convert linked list to slice for comparison
func listToSlice(head *ListNode) []int {
  var result []int
  for head != nil {
    result = append(result, head.Val)
    head = head.Next
  }
  return result
}

// Test cases
func main() {
  // Test 1: Reverse middle portion
  head1 := createList([]int{1, 2, 3, 4, 5})
  result1 := reverseBetween(head1, 2, 4)
  fmt.Println("Test 1:", listToSlice(result1)) // [1 4 3 2 5]

  // Test 2: Single node (no reversal)
  head2 := createList([]int{5})
  result2 := reverseBetween(head2, 1, 1)
  fmt.Println("Test 2:", listToSlice(result2)) // [5]

  // Test 3: Reverse entire list
  head3 := createList([]int{1, 2})
  result3 := reverseBetween(head3, 1, 2)
  fmt.Println("Test 3:", listToSlice(result3)) // [2 1]

  // Test 4: Reverse from start
  head4 := createList([]int{1, 2, 3, 4, 5})
  result4 := reverseBetween(head4, 1, 3)
  fmt.Println("Test 4:", listToSlice(result4)) // [3 2 1 4 5]

  // Test 5: Reverse at end
  head5 := createList([]int{1, 2, 3, 4, 5})
  result5 := reverseBetween(head5, 3, 5)
  fmt.Println("Test 5:", listToSlice(result5)) // [1 2 5 4 3]
}

Approach 2: Recursive

elegant

Recursively advance to position left. At that point, reverse nodes one at a time as the call stack unwinds, tracking when to stop at position right.

⏱ Time O(n) Traverse to left, reverse to right 💾 Space O(n) Recursion call stack

Key Insight

Instead of explicit pointer swaps, recursion naturally tracks the “current position.” When we reach position left, we begin the reversal. As we unwind (backtrack), we reverse links and stop after right - left reversals.

Step-by-step Example

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

Step	Depth	Node	Action
Go deep	1	Node 1	Recurse to node 2
Go deep	2	Node 2	Recurse to node 3 (mark as reversal start)
Go deep	3	Node 3	Recurse to node 4
Go deep	4	Node 4	Recurse to node 5
Unwind	4	Node 4→5	Reverse: 4.next.next = 4 (stop here, right=4)
Unwind	3	Node 3→4	Reverse: 3.next.next = 3
Unwind	2	Node 2→3	Reverse: 2.next.next = 2 (tail of reversed section)
Unwind	1	Node 1→2	Connect tail; return

Pseudocode

function reverseBetween(head, left, right):
    if left == 1:
        return reverseN(head, right)
    else:
        head.next = reverseBetween(head.next, left - 1, right - 1)
        return head

function reverseN(head, n):
    if n == 1:
        return head

    new_head = reverseN(head.next, n - 1)
    head.next.next = head
    head.next = successor
    return new_head

Solution Code

Python

reverse_linked_list_ii_recursive.py

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# Global variable to track the successor node
successor = None


def reverseBetween(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    """
    Reverse a portion of a linked list from position left to right using recursion.

    Time Complexity: O(n) - traverse to left, then reverse to right
    Space Complexity: O(n) - recursion call stack

    Strategy:
    1. If left == 1, call reverseN() to reverse the first 'right' nodes
    2. Otherwise, recursively process the next node with adjusted positions
    3. Use a global successor variable to track where to stop reversing
    """
    if left == 1:
        return reverseN(head, right)
    else:
        # Recursively process the rest of the list
        head.next = reverseBetween(head.next, left - 1, right - 1)
        return head


def reverseN(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    """
    Reverse the first n nodes of a linked list.

    The global 'successor' variable tracks the node after the nth node,
    which becomes the tail of the reversed sublist.
    """
    global successor

    if n == 1:
        # Base case: mark successor as the node after the first node
        successor = head.next
        return head

    # Recursively reverse the rest
    new_head = reverseN(head.next, n - 1)

    # At this point, head.next points to the (n-1)th node
    # We want to reverse: head.next.next = head
    head.next.next = head

    # Connect head to successor (the node after position n)
    head.next = successor

    return new_head


# Test cases
def list_to_array(head: Optional[ListNode]) -> list:
    """Convert linked list to array for easy comparison."""
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result


def array_to_list(arr: list) -> Optional[ListNode]:
    """Convert array to linked list."""
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


# Test 1: Reverse middle portion
head1 = array_to_list([1, 2, 3, 4, 5])
result1 = reverseBetween(head1, 2, 4)
print(list_to_array(result1))  # [1, 4, 3, 2, 5]

# Test 2: Single node (no reversal)
head2 = array_to_list([5])
result2 = reverseBetween(head2, 1, 1)
print(list_to_array(result2))  # [5]

# Test 3: Reverse entire list
head3 = array_to_list([1, 2])
result3 = reverseBetween(head3, 1, 2)
print(list_to_array(result3))  # [2, 1]

# Test 4: Reverse from start
head4 = array_to_list([1, 2, 3, 4, 5])
result4 = reverseBetween(head4, 1, 3)
print(list_to_array(result4))  # [3, 2, 1, 4, 5]

# Test 5: Reverse at end
head5 = array_to_list([1, 2, 3, 4, 5])
result5 = reverseBetween(head5, 3, 5)
print(list_to_array(result5))  # [1, 2, 5, 4, 3]

C++

reverse_linked_list_ii_recursive.cpp

#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Global pointer to track the successor node
ListNode* successor = nullptr;

/**
 * Reverse the first n nodes of a linked list.
 *
 * The global 'successor' variable tracks the node after the nth node,
 * which becomes the tail of the reversed sublist.
 */
ListNode* reverseN(ListNode* head, int n) {
    if (n == 1) {
        // Base case: mark successor as the node after the first node
        successor = head->next;
        return head;
    }

    // Recursively reverse the rest
    ListNode* new_head = reverseN(head->next, n - 1);

    // At this point, head->next points to the (n-1)th node
    // We want to reverse: head->next->next = head
    head->next->next = head;

    // Connect head to successor (the node after position n)
    head->next = successor;

    return new_head;
}

/**
 * Reverse a portion of a linked list from position left to right using recursion.
 *
 * Time Complexity: O(n) - traverse to left, then reverse to right
 * Space Complexity: O(n) - recursion call stack
 *
 * Strategy:
 * 1. If left == 1, call reverseN() to reverse the first 'right' nodes
 * 2. Otherwise, recursively process the next node with adjusted positions
 */
ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (left == 1) {
        return reverseN(head, right);
    } else {
        // Recursively process the rest of the list
        head->next = reverseBetween(head->next, left - 1, right - 1);
        return head;
    }
}

// Helper function to create a linked list from a vector
ListNode* createList(const vector<int>& values) {
    if (values.empty()) return nullptr;
    ListNode* head = new ListNode(values[0]);
    ListNode* current = head;
    for (int i = 1; i < values.size(); i++) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    return head;
}

// Helper function to print a linked list
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << "\n";
}

// Helper function to delete a linked list
void deleteList(ListNode* head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

// Test cases
int main() {
    // Test 1: Reverse middle portion
    ListNode* head1 = createList({1, 2, 3, 4, 5});
    ListNode* result1 = reverseBetween(head1, 2, 4);
    cout << "Test 1: ";
    printList(result1);  // 1 4 3 2 5
    deleteList(result1);

    // Test 2: Single node (no reversal)
    ListNode* head2 = createList({5});
    ListNode* result2 = reverseBetween(head2, 1, 1);
    cout << "Test 2: ";
    printList(result2);  // 5
    deleteList(result2);

    // Test 3: Reverse entire list
    ListNode* head3 = createList({1, 2});
    ListNode* result3 = reverseBetween(head3, 1, 2);
    cout << "Test 3: ";
    printList(result3);  // 2 1
    deleteList(result3);

    // Test 4: Reverse from start
    ListNode* head4 = createList({1, 2, 3, 4, 5});
    ListNode* result4 = reverseBetween(head4, 1, 3);
    cout << "Test 4: ";
    printList(result4);  // 3 2 1 4 5
    deleteList(result4);

    // Test 5: Reverse at end
    ListNode* head5 = createList({1, 2, 3, 4, 5});
    ListNode* result5 = reverseBetween(head5, 3, 5);
    cout << "Test 5: ";
    printList(result5);  // 1 2 5 4 3
    deleteList(result5);

    return 0;
}

Java

reverse_linked_list_ii_recursive.java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Reverse a portion of a linked list from position left to right using recursion.
 *
 * Time Complexity: O(n) - traverse to left, then reverse to right
 * Space Complexity: O(n) - recursion call stack
 */
class Solution {
    // Global variable to track the successor node
    private ListNode successor = null;

    /**
     * Reverse the first n nodes of a linked list.
     *
     * The global 'successor' variable tracks the node after the nth node,
     * which becomes the tail of the reversed sublist.
     */
    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // Base case: mark successor as the node after the first node
            successor = head.next;
            return head;
        }

        // Recursively reverse the rest
        ListNode newHead = reverseN(head.next, n - 1);

        // At this point, head.next points to the (n-1)th node
        // We want to reverse: head.next.next = head
        head.next.next = head;

        // Connect head to successor (the node after position n)
        head.next = successor;

        return newHead;
    }

    /**
     * Reverse a portion of a linked list from position left to right.
     *
     * Strategy:
     * 1. If left == 1, call reverseN() to reverse the first 'right' nodes
     * 2. Otherwise, recursively process the next node with adjusted positions
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            return reverseN(head, right);
        } else {
            // Recursively process the rest of the list
            head.next = reverseBetween(head.next, left - 1, right - 1);
            return head;
        }
    }
}

// Test harness
public class reverse_linked_list_ii_recursive {
    // Helper function to create a linked list from an array
    static ListNode createList(int[] values) {
        if (values.length == 0) return null;
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    // Helper function to convert linked list to array for comparison
    static List<Integer> listToArray(ListNode head) {
        List<Integer> result = new ArrayList<>();
        while (head != null) {
            result.add(head.val);
            head = head.next;
        }
        return result;
    }

    // Helper function to print a linked list
    static void printList(ListNode head) {
        List<Integer> values = listToArray(head);
        System.out.println(values);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // Test 1: Reverse middle portion
        ListNode head1 = createList(new int[]{1, 2, 3, 4, 5});
        ListNode result1 = solution.reverseBetween(head1, 2, 4);
        System.out.print("Test 1: ");
        printList(result1);  // [1, 4, 3, 2, 5]

        // Test 2: Single node (no reversal)
        ListNode head2 = createList(new int[]{5});
        ListNode result2 = solution.reverseBetween(head2, 1, 1);
        System.out.print("Test 2: ");
        printList(result2);  // [5]

        // Test 3: Reverse entire list
        ListNode head3 = createList(new int[]{1, 2});
        ListNode result3 = solution.reverseBetween(head3, 1, 2);
        System.out.print("Test 3: ");
        printList(result3);  // [2, 1]

        // Test 4: Reverse from start
        ListNode head4 = createList(new int[]{1, 2, 3, 4, 5});
        ListNode result4 = solution.reverseBetween(head4, 1, 3);
        System.out.print("Test 4: ");
        printList(result4);  // [3, 2, 1, 4, 5]

        // Test 5: Reverse at end
        ListNode head5 = createList(new int[]{1, 2, 3, 4, 5});
        ListNode result5 = solution.reverseBetween(head5, 3, 5);
        System.out.print("Test 5: ");
        printList(result5);  // [1, 2, 5, 4, 3]
    }
}

JavaScript

reverse_linked_list_ii_recursive.js

/**
 * Definition for singly-linked list node
 */
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Reverse a portion of a linked list from position left to right using recursion.
 *
 * Time Complexity: O(n) - traverse to left, then reverse to right
 * Space Complexity: O(n) - recursion call stack
 *
 * Strategy:
 * 1. If left == 1, call reverseN() to reverse the first 'right' nodes
 * 2. Otherwise, recursively process the next node with adjusted positions
 */

// Global variable to track the successor node
let successor = null;

/**
 * Reverse the first n nodes of a linked list.
 *
 * The global 'successor' variable tracks the node after the nth node,
 * which becomes the tail of the reversed sublist.
 *
 * @param {ListNode} head - Head of the list
 * @param {number} n - Number of nodes to reverse
 * @return {ListNode} - New head after reversal
 */
function reverseN(head, n) {
    if (n === 1) {
        // Base case: mark successor as the node after the first node
        successor = head.next;
        return head;
    }

    // Recursively reverse the rest
    const newHead = reverseN(head.next, n - 1);

    // At this point, head.next points to the (n-1)th node
    // We want to reverse: head.next.next = head
    head.next.next = head;

    // Connect head to successor (the node after position n)
    head.next = successor;

    return newHead;
}

/**
 * Reverse a portion of a linked list from position left to right.
 *
 * @param {ListNode} head - The head of the linked list
 * @param {number} left - Starting position (1-indexed)
 * @param {number} right - Ending position (1-indexed)
 * @return {ListNode} - The head of the modified list
 */
function reverseBetween(head, left, right) {
    if (left === 1) {
        return reverseN(head, right);
    } else {
        // Recursively process the rest of the list
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
}

// Helper function to create a linked list from an array
function createList(values) {
    if (values.length === 0) return null;
    const head = new ListNode(values[0]);
    let current = head;
    for (let i = 1; i < values.length; i++) {
        current.next = new ListNode(values[i]);
        current = current.next;
    }
    return head;
}

// Helper function to convert linked list to array for comparison
function listToArray(head) {
    const result = [];
    while (head !== null) {
        result.push(head.val);
        head = head.next;
    }
    return result;
}

// Test cases
// Test 1: Reverse middle portion
let head1 = createList([1, 2, 3, 4, 5]);
successor = null;
let result1 = reverseBetween(head1, 2, 4);
console.log('Test 1:', listToArray(result1));  // [1, 4, 3, 2, 5]

// Test 2: Single node (no reversal)
let head2 = createList([5]);
successor = null;
let result2 = reverseBetween(head2, 1, 1);
console.log('Test 2:', listToArray(result2));  // [5]

// Test 3: Reverse entire list
let head3 = createList([1, 2]);
successor = null;
let result3 = reverseBetween(head3, 1, 2);
console.log('Test 3:', listToArray(result3));  // [2, 1]

// Test 4: Reverse from start
let head4 = createList([1, 2, 3, 4, 5]);
successor = null;
let result4 = reverseBetween(head4, 1, 3);
console.log('Test 4:', listToArray(result4));  // [3, 2, 1, 4, 5]

// Test 5: Reverse at end
let head5 = createList([1, 2, 3, 4, 5]);
successor = null;
let result5 = reverseBetween(head5, 3, 5);
console.log('Test 5:', listToArray(result5));  // [1, 2, 5, 4, 3]

module.exports = { reverseBetween, reverseN };

Rust

reverse_linked_list_ii_recursive.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

/**
 * Reverse a portion of a linked list from position left to right using recursion.
 *
 * Time Complexity: O(n) - traverse to left, then reverse to right
 * Space Complexity: O(n) - recursion call stack
 *
 * Strategy:
 * 1. If left == 1, call reverseN() to reverse the first 'right' nodes
 * 2. Otherwise, recursively process the next node with adjusted positions
 */

/**
 * Helper function to reverse the first n nodes of a linked list.
 *
 * Returns (new_head, tail_node) where new_head is the head after reversal
 * and tail_node should be connected to the successor.
 */
fn reverse_n(
    head: Option<Rc<RefCell<ListNode>>>,
    n: i32,
) -> (Option<Rc<RefCell<ListNode>>>, Option<Rc<RefCell<ListNode>>>) {
    match head {
        Some(node) => {
            if n == 1 {
                // Base case: return the head and its next as successor
                let successor = node.borrow_mut().next.take();
                (Some(node), successor)
            } else {
                // Recursively reverse the rest
                let next_node = node.borrow_mut().next.take();
                let (new_head, successor) = reverse_n(next_node, n - 1);

                // Reconstruct the reversal
                if let Some(ref head_ref) = new_head {
                    // Find the current node's position in the reversed chain
                    // We need to connect it properly
                    let mut curr = head_ref.clone();
                    for _ in 1..n - 1 {
                        if let Some(ref next_ref) = curr.borrow().next {
                            curr = next_ref.clone();
                        }
                    }

                    // curr is now the tail of reversed section up to n-1
                    curr.borrow_mut().next = Some(node.clone());
                }

                node.borrow_mut().next = successor;
                (new_head, Some(node))
            }
        }
        None => (None, None),
    }
}

pub fn reverse_between(
    head: Option<Rc<RefCell<ListNode>>>,
    left: i32,
    right: i32,
) -> Option<Rc<RefCell<ListNode>>> {
    if left == right {
        return head;
    }

    if left == 1 {
        // Reverse the first 'right' nodes
        let (new_head, _) = reverse_n(head, right);
        new_head
    } else {
        // Recursively process the rest of the list
        match head {
            Some(node) => {
                let next = node.borrow_mut().next.take();
                let reversed_next = reverse_between(next, left - 1, right - 1);
                node.borrow_mut().next = reversed_next;
                Some(node)
            }
            None => None,
        }
    }
}

// Alternative cleaner recursive implementation using manual tracking
pub fn reverse_between_v2(
    head: Option<Rc<RefCell<ListNode>>>,
    left: i32,
    right: i32,
) -> Option<Rc<RefCell<ListNode>>> {
    fn reverse_range(
        node: Option<Rc<RefCell<ListNode>>>,
        left: i32,
        right: i32,
        pos: i32,
    ) -> Option<Rc<RefCell<ListNode>>> {
        match node {
            Some(mut n) => {
                let node_ref = Rc::get_mut(&mut n)?;
                if left == 1 {
                    // Start reversing
                    let (reversed, _) = reverse_first_n(Some(n), right);
                    reversed
                } else {
                    // Continue traversing
                    let next = std::mem::take(&mut node_ref.next);
                    node_ref.next = reverse_range(next, left - 1, right - 1, pos + 1);
                    Some(n)
                }
            }
            None => None,
        }
    }

    fn reverse_first_n(
        head: Option<Rc<RefCell<ListNode>>>,
        n: i32,
    ) -> (Option<Rc<RefCell<ListNode>>>, Option<Rc<RefCell<ListNode>>>) {
        match head {
            Some(mut node) => {
                let node_ref = Rc::get_mut(&mut node).unwrap();
                if n == 1 {
                    let succ = std::mem::take(&mut node_ref.next);
                    (Some(node), succ)
                } else {
                    let next = std::mem::take(&mut node_ref.next);
                    let (new_head, succ) = reverse_first_n(next, n - 1);

                    if let Some(ref nh) = new_head {
                        let mut curr = nh.clone();
                        for _ in 1..n - 1 {
                            if let Some(ref next_ref) = curr.borrow().next {
                                curr = next_ref.clone();
                            }
                        }
                        curr.borrow_mut().next = Some(node.clone());
                    }

                    node_ref.next = succ;
                    (new_head, Some(node))
                }
            }
            None => (None, None),
        }
    }

    reverse_range(head, left, right, 1)
}

// Helper function to create a linked list from a vector
fn create_list(values: Vec<i32>) -> Option<Rc<RefCell<ListNode>>> {
    if values.is_empty() {
        return None;
    }

    let mut head = Rc::new(RefCell::new(ListNode::new(values[0])));
    let mut current = head.clone();

    for val in &values[1..] {
        let new_node = Rc::new(RefCell::new(ListNode::new(*val)));
        current.borrow_mut().next = Some(new_node.clone());
        current = new_node;
    }

    Some(head)
}

// Helper function to convert linked list to vector
fn list_to_vec(head: Option<Rc<RefCell<ListNode>>>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut current = head;

    while let Some(node) = current {
        result.push(node.borrow().val);
        current = node.borrow_mut().next.take();
    }

    result
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_reverse_middle_portion() {
        let head = create_list(vec![1, 2, 3, 4, 5]);
        let result = reverse_between(head, 2, 4);
        assert_eq!(list_to_vec(result), vec![1, 4, 3, 2, 5]);
    }

    #[test]
    fn test_single_node() {
        let head = create_list(vec![5]);
        let result = reverse_between(head, 1, 1);
        assert_eq!(list_to_vec(result), vec![5]);
    }

    #[test]
    fn test_reverse_entire_list() {
        let head = create_list(vec![1, 2]);
        let result = reverse_between(head, 1, 2);
        assert_eq!(list_to_vec(result), vec![2, 1]);
    }

    #[test]
    fn test_reverse_from_start() {
        let head = create_list(vec![1, 2, 3, 4, 5]);
        let result = reverse_between(head, 1, 3);
        assert_eq!(list_to_vec(result), vec![3, 2, 1, 4, 5]);
    }

    #[test]
    fn test_reverse_at_end() {
        let head = create_list(vec![1, 2, 3, 4, 5]);
        let result = reverse_between(head, 3, 5);
        assert_eq!(list_to_vec(result), vec![1, 2, 5, 4, 3]);
    }
}

fn main() {
    // Test 1: Reverse middle portion
    let head1 = create_list(vec![1, 2, 3, 4, 5]);
    let result1 = reverse_between(head1, 2, 4);
    println!("Test 1: {:?}", list_to_vec(result1));  // [1, 4, 3, 2, 5]

    // Test 2: Single node (no reversal)
    let head2 = create_list(vec![5]);
    let result2 = reverse_between(head2, 1, 1);
    println!("Test 2: {:?}", list_to_vec(result2));  // [5]

    // Test 3: Reverse entire list
    let head3 = create_list(vec![1, 2]);
    let result3 = reverse_between(head3, 1, 2);
    println!("Test 3: {:?}", list_to_vec(result3));  // [2, 1]

    // Test 4: Reverse from start
    let head4 = create_list(vec![1, 2, 3, 4, 5]);
    let result4 = reverse_between(head4, 1, 3);
    println!("Test 4: {:?}", list_to_vec(result4));  // [3, 2, 1, 4, 5]

    // Test 5: Reverse at end
    let head5 = create_list(vec![1, 2, 3, 4, 5]);
    let result5 = reverse_between(head5, 3, 5);
    println!("Test 5: {:?}", list_to_vec(result5));  // [1, 2, 5, 4, 3]
}

Go

reverse_linked_list_ii_recursive.go

package main

import "fmt"

type ListNode struct {
  Val  int
  Next *ListNode
}

/**
 * Reverse a portion of a linked list from position left to right using recursion.
 *
 * Time Complexity: O(n) - traverse to left, then reverse to right
 * Space Complexity: O(n) - recursion call stack
 *
 * Strategy:
 * 1. If left == 1, call reverseN() to reverse the first 'right' nodes
 * 2. Otherwise, recursively process the next node with adjusted positions
 */

// Global variable to track the successor node
var successor *ListNode

/**
 * Reverse the first n nodes of a linked list.
 *
 * The global 'successor' variable tracks the node after the nth node,
 * which becomes the tail of the reversed sublist.
 */
func reverseN(head *ListNode, n int) *ListNode {
  if n == 1 {
    // Base case: mark successor as the node after the first node
    successor = head.Next
    return head
  }

  // Recursively reverse the rest
  newHead := reverseN(head.Next, n-1)

  // At this point, head.Next points to the (n-1)th node
  // We want to reverse: head.Next.Next = head
  head.Next.Next = head

  // Connect head to successor (the node after position n)
  head.Next = successor

  return newHead
}

/**
 * Reverse a portion of a linked list from position left to right.
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
  if left == 1 {
    return reverseN(head, right)
  } else {
    // Recursively process the rest of the list
    head.Next = reverseBetween(head.Next, left-1, right-1)
    return head
  }
}

// Helper function to create a linked list from a slice
func createList(values []int) *ListNode {
  if len(values) == 0 {
    return nil
  }
  head := &ListNode{Val: values[0]}
  current := head
  for i := 1; i < len(values); i++ {
    current.Next = &ListNode{Val: values[i]}
    current = current.Next
  }
  return head
}

// Helper function to convert linked list to slice for comparison
func listToSlice(head *ListNode) []int {
  var result []int
  for head != nil {
    result = append(result, head.Val)
    head = head.Next
  }
  return result
}

// Test cases
func main() {
  // Test 1: Reverse middle portion
  head1 := createList([]int{1, 2, 3, 4, 5})
  successor = nil
  result1 := reverseBetween(head1, 2, 4)
  fmt.Println("Test 1:", listToSlice(result1)) // [1 4 3 2 5]

  // Test 2: Single node (no reversal)
  head2 := createList([]int{5})
  successor = nil
  result2 := reverseBetween(head2, 1, 1)
  fmt.Println("Test 2:", listToSlice(result2)) // [5]

  // Test 3: Reverse entire list
  head3 := createList([]int{1, 2})
  successor = nil
  result3 := reverseBetween(head3, 1, 2)
  fmt.Println("Test 3:", listToSlice(result3)) // [2 1]

  // Test 4: Reverse from start
  head4 := createList([]int{1, 2, 3, 4, 5})
  successor = nil
  result4 := reverseBetween(head4, 1, 3)
  fmt.Println("Test 4:", listToSlice(result4)) // [3 2 1 4 5]

  // Test 5: Reverse at end
  head5 := createList([]int{1, 2, 3, 4, 5})
  successor = nil
  result5 := reverseBetween(head5, 3, 5)
  fmt.Println("Test 5:", listToSlice(result5)) // [1 2 5 4 3]
}

Watch for these pitfalls

• 1-indexed positions: Forget that left and right are 1-indexed, and your loops will be off by one.
• Dummy node importance: Without a dummy node, reversing from position 1 requires special handling; the dummy eliminates this edge case.
• Tail connection: Ensure the node before position left still points to the node before position right+1 after reversal. The dummy and pointer tracking handle this.
• Recursion stack depth: For very large n and large reversal ranges, recursion may hit stack limits. The iterative approach is safer for production.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

reverse_linked_list_ii_space_optimized.py

"""
Solution for Reverse Linked List II
"""

def solve():
    """Implementation for approach 3 of Reverse Linked List II"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

reverse_linked_list_ii_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Reverse Linked List II
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

ReverseLinkedListIiSpaceOptimized.java

/**
 * Solution for Reverse Linked List II
 * Approach 3
 */
public class ReverseLinkedListIiSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

reverse_linked_list_ii_space_optimized.js

/**
 * Solution for Reverse Linked List II
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

reverse_linked_list_ii_space_optimized.rs

/// Solution for Reverse Linked List II
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

reverse_linked_list_ii_space_optimized.go

package main

import "fmt"

// Solution for Reverse Linked List II
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Reverse Nodes in k-Group ↗ Hard #25
• Reverse Linked List ↗ Easy #206
• Swap Nodes in Pairs ↗ Medium #24
• Odd Even Linked List ↗ Medium #328

Interview Tips

Key trade-offs to discuss

• Why iterative? It is O(1) space and avoids recursion depth limits — the safest production choice.
• Why recursive? It is more elegant and showcases understanding of recursion and backtracking — great for demonstrating depth.
• Dummy node trick: Mention this pattern applies to many linked list problems (removing nodes, reversing, etc.).
• Edge cases: Always test left=1 (reversal at head), right=n (reversal at tail), and left=right (no reversal).
• Pointer safety: Talk about null checks — ensure curr.next exists before accessing it.

← Previous
#86 Partition List Next
#97 Interleaving String →