Reverse Linked List II

Reverse a linked list from position left to right (1-based), and return the head of the modified list.

Why this is worth learning

An anchor before the segment lets repeated head insertion reverse only the selected region. The original first segment node becomes its stable tail.

Before coding: one-minute experiment

For 1→2→3→4→5 with left=2 and right=4, which node becomes the tail of the reversed segment?

Function signature

func ReverseBetween(head *ListNode, left int, right int) *ListNode

Inputs / outputs

• head: head of the list.
• left, right: positions to reverse, 1 <= left <= right.
• Return: head of the list after reversal.

Example

head = 1 -> 2 -> 3 -> 4 -> 5, left = 2, right = 4
Output: 1 -> 4 -> 3 -> 2 -> 5

Constraints

• 1 <= number of nodes <= 100_000
• 1 <= left <= right <= number of nodes; positions are one-based.

Core idea (near-solution)

Reversing the whole list would destroy the order outside the requested segment. Record its predecessor and leave it fixed. The original segment head will become the segment tail; repeatedly detach the node immediately after it and insert that node after the predecessor. Each move grows the reversed part without losing the suffix. For positions 2..4 in A→B→C→D→E, moving C gives A→C→B→D→E; moving D gives A→D→C→B→E. A dummy supplies the same predecessor operation when left=1.

Invariant: The prefix before prev is untouched; prev.Next begins the growing reversed segment, cur is its fixed tail, and cur.Next still reaches the unprocessed suffix.

Algorithm (step-by-step)

1. Create dummy -> head and move prev to the node before left.
2. Reverse the sublist using head-insertion:
   • curr = prev.Next
   • For each node after curr in the range, move it to the front of the sublist.
3. Return dummy.Next.

Correctness sketch

Move prev to the node immediately before the one-based left position, using a dummy when left=1. Let cur remain the original first node of the segment. After k insertions, the first k+1 selected nodes appear in reversed order after prev, cur is their tail, and the unprocessed suffix still follows cur. Detach cur.Next and insert it immediately after prev; this extends the reversed selected prefix by one without touching nodes outside the segment. Repeating right-left times reverses exactly the requested positions. The saved anchor and stable tail reconnect the unchanged prefix and suffix automatically.

Trace (hand walkthrough)

Example input:
head = 1 -> 2 -> 3 -> 4 -> 5, left = 2, right = 4
Output: 1 -> 4 -> 3 -> 2 -> 5

Walk:
- prev is node 1; curr is node 2 and will remain the segment tail
- move=3: set 2.Next=4, 3.Next=2, 1.Next=3 -> 1->3->2->4->5
- move=4: set 2.Next=5, 4.Next=3, 1.Next=4 -> 1->4->3->2->5
- two insertions = right-left; nodes 1 and 5 remain outside the reversed segment

Pitfalls to avoid

• Failing to reconnect the tail after reversal.
• Off-by-one errors in the reversal length.

Debugging lens

Test left=1, right=length, and left=right. Positions are one-based and valid: 1<=left<=right<=list length. Verify original node reuse and no cycles.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Use a dummy head and move prev to the node before left.
• Reverse by repeatedly moving the then node to the front of the sublist.

Reconstruction checkpoint

On A→B→C→D→E, reverse positions 2 through 4 using head insertion. What is the list after each move, which node stays the segment tail, and where does it point at the end?

Return to Linked List · Module quiz