Reverse Linked List II

Difficulty: Medium Source: NeetCode

Problem

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. Positions are 1-indexed.

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Reversing a Linked List — in-place pointer reversal with prev/curr (see problem 1)
• Dummy Head Trick — sentinel node to handle edge cases like reversing from position 1
• Pointer Re-attachment — connecting reversed sublist back to the surrounding nodes

1. Brute Force — Collect and Rebuild

Intuition

Extract the values in the subrange, reverse them, then put them back. Not the most elegant, but easy to reason about and good for verifying the optimal approach.

Algorithm

1. Walk the list and collect all node values into a Python list.
2. Reverse the slice values[left-1:right] in-place.
3. Walk the original list again and overwrite each node’s .val with the new values.

Solution

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

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

def reverseBetween_brute(head, left, right):
    values = []
    cur = head
    while cur:
        values.append(cur.val)
        cur = cur.next

    # Reverse the slice [left-1, right) in-place
    l, r = left - 1, right - 1
    while l < r:
        values[l], values[r] = values[r], values[l]
        l += 1
        r -= 1

    # Write values back into nodes
    cur = head
    for v in values:
        cur.val = v
        cur = cur.next

    return head

# Test cases
head = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(reverseBetween_brute(head, 2, 4))  # 1->4->3->2->5

head2 = build_list([5])
print("Output: ", end=""); print_list(reverseBetween_brute(head2, 1, 1))  # 5

head3 = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(reverseBetween_brute(head3, 1, 5))  # 5->4->3->2->1

Complexity

• Time: O(n) — two passes
• Space: O(n) — storing all values

2. In-Place with Dummy Head (Optimal)

Intuition

We want to reverse exactly the nodes from position left to right without touching anything else. The key is to identify four anchor points:

• prev_left: the node just before position left (we’ll re-attach the reversed segment here)
• The node at position left (it becomes the tail of the reversed segment)
• The node at position right (it becomes the new head of the reversed segment)
• The node just after position right (we’ll re-attach to the tail of the reversed segment)

Using a dummy head means prev_left always exists, even when left = 1.

Example: [1, 2, 3, 4, 5], left=2, right=4

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
         ^    ^              ^    ^
      prev_l  left_node  right  after_right
       (pos 1) (pos 2)  (pos 4) (pos 5)

After reversing positions 2-4:
dummy -> 1 -> 4 -> 3 -> 2 -> 5 -> None
                        ^    ^
                   left_node after_right
                   (now tail)

Algorithm

1. Create a dummy node and set dummy.next = head.
2. Walk left - 1 steps from dummy to find prev_left (the node before position left).
3. Set left_node = prev_left.next (the node at position left).
4. Reverse the sublist from position left to right using standard iterative reversal. Keep count.
5. Re-attach: prev_left.next = right_node (the new head of the reversed segment) and left_node.next = after_right.
6. Return dummy.next.

Solution

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

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

def reverseBetween(head, left, right):
    dummy = ListNode(0, head)

    # Step 1: Walk to the node just before position 'left'
    prev_left = dummy
    for _ in range(left - 1):
        prev_left = prev_left.next

    # Step 2: 'left_node' is the node at position 'left'
    # It will become the tail of the reversed segment
    left_node = prev_left.next

    # Step 3: Reverse from position left to right
    # We reverse (right - left) times
    prev = None
    cur = left_node
    for _ in range(right - left + 1):
        next_node = cur.next
        cur.next = prev
        prev = cur
        cur = next_node
    # After loop:
    # prev = node at position 'right' (new head of reversed segment)
    # cur  = node at position 'right+1' (first node after the segment)

    # Step 4: Re-attach
    prev_left.next = prev       # connect node before segment to new head
    left_node.next = cur        # connect old left (now tail) to node after segment

    return dummy.next

# Test cases
head = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(reverseBetween(head, 2, 4))  # 1->4->3->2->5

head2 = build_list([5])
print("Output: ", end=""); print_list(reverseBetween(head2, 1, 1))  # 5

# left=1: reverse from the very start (dummy saves us here)
head3 = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(reverseBetween(head3, 1, 5))  # 5->4->3->2->1

head4 = build_list([3, 5])
print("Output: ", end=""); print_list(reverseBetween(head4, 1, 2))  # 5->3

Complexity

• Time: O(n) — at most two passes: one to find prev_left, one to reverse
• Space: O(1) — only pointer variables

Common Pitfalls

Not using a dummy node when left = 1. If the reversal starts at the head, there’s no “node before position left”. The dummy node acts as a fake predecessor so the re-attachment code stays uniform.

Getting confused about prev and cur after the reversal loop. After reversing right - left + 1 nodes, prev points to the node that was at position right (now the start of the reversed segment) and cur points to the node that was at position right + 1 (the first node after the segment). Keep this straight for the re-attachment.

Forgetting to re-attach left_node.next. After reversal, left_node (original position-left node) has next = None (or whatever prev started as). You must set left_node.next = cur to reconnect it to the rest of the list.