Reverse Linked List II — Solution

Problem

Given the head of a singly linked list and two 1-indexed positions left and right, reverse only the nodes between those two positions and return the modified list. Everything before position left and after position right remains in its original order.

[1,2,3,4,5]

• Input: head = [1,2,3,4,5], left = 2, right = 4
• Output: [1,4,3,2,5]
• Explanation: The sublist from position 2 to 4 is reversed in place; nodes 1 and 5 are untouched.

Intuition

The challenge is reversing a bounded section without disturbing the rest of the list. The key insight is to locate the node just before position left — call it the anchor — then repeatedly peel off the node immediately after curr and drop it right after the anchor. Each relocation prepends one more element to the growing reversed section, so the entire reversal completes in a single pass with no extra memory.

Approach 1 — Collect, Reverse, Overwrite

Gather every node value into an array, reverse the slice from index left-1 to right-1, then walk the list a second time writing the values back. The structure of the list never changes — only the values inside nodes are swapped.

1. Traverse the list once, appending each node's value to an array.
2. Use two indices left_idx = left - 1 and right_idx = right - 1, swapping inward until they meet.
3. Walk the list again, overwriting each node's value from the array in order.
4. Return head — the same node that came in, now with rearranged values.

1def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
2    values = []
3    curr = head
4    while curr:
5        values.append(curr.val)
6        curr = curr.next
7
8    left_idx, right_idx = left - 1, right - 1
9    while left_idx < right_idx:
10        values[left_idx], values[right_idx] = values[right_idx], values[left_idx]
11        left_idx += 1
12        right_idx -= 1
13
14    curr = head
15    for val in values:
16        curr.val = val
17        curr = curr.next
18
19    return head

Time: O(n) — two full traversals plus an O(right − left) swap pass, all linear.
Space: O(n) — the auxiliary array stores every node's value.

Approach 2 — In-Place Insertion (Optimal)

Attach a dummy node before head so that prev always has a predecessor regardless of whether left = 1. Advance prev to the node just before the reversal region, then repeat right − left times: peel off the node immediately after curr and splice it in right after prev. Each step prepends one more element to the reversed section. curr never moves — it is the permanent tail of the reversed portion.

1. Create a dummy node with dummy.next = head to avoid special-casing left = 1.
2. Advance prev exactly left - 1 steps so it sits at the node just before the reversal region.
3. Set curr = prev.next — this node becomes the fixed tail of the reversed section.
4. Repeat right - left times: save next_node = curr.next, unlink it, then splice it directly after prev.
5. Return dummy.next.

1def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
2    dummy = ListNode(0)
3    dummy.next = head
4    prev = dummy
5
6    for _ in range(left - 1):      # stop just before the reversal region
7        prev = prev.next
8
9    curr = prev.next               # permanent tail of the reversed section
10
11    for _ in range(right - left):  # relocate right-left nodes to the front, one at a time
12        next_node = curr.next          # node about to be moved
13        curr.next = next_node.next     # unlink next_node from its current position
14        next_node.next = prev.next     # next_node will precede what is currently at the front
15        prev.next = next_node          # anchor now points to the newly prepended node
16
17    return dummy.next

Time: O(n) — one pass to position prev, then O(right − left) ≤ O(n) constant-work insertions.
Space: O(1) — only a fixed number of pointer variables; no auxiliary data structure.

Complexity Summary

Common Mistakes

• Skipping the dummy head: without it, left = 1 leaves prev with no node before the list to reference; the dummy node eliminates this edge case so both paths are identical.
• Wrong inner loop count: the loop runs right − left times, not right − left + 1. The sublist contains right − left + 1 nodes but curr stays pinned as the tail; only the nodes ahead of it are relocated.
• Reading curr.next too late: next_node = curr.next must be captured before curr.next is overwritten on the very next line — reversing that order permanently loses the reference to the rest of the list.
• Advancing curr inside the loop: curr is intentionally fixed as the growing tail of the reversed section; moving it forward each step detaches nodes from the chain instead of prepending them.
• Off-by-one on the prev walk: starting from the dummy node, the loop runs exactly left − 1 iterations. After 0 steps you are at the dummy (before position 1); after left − 1 steps you are at position left − 1, which is just before the reversal region.

Related Problems

• Reverse Linked List — reverses the entire list; the pointer-flip mechanics here are a direct prerequisite
• Reverse Nodes in k-Group — applies the same in-place reversal logic to every consecutive k-length chunk
• Swap Nodes in Pairs — a specific case of this problem where left=1, right=2, then left=3, right=4, and so on
• Reorder List — requires O(1)-space linked list manipulation, including a reversal of the back half
• Rotate List — no reversal, but uses the same dummy-head and positional pointer-walk pattern