Reverse Linked List II

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

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

Core idea (near-solution)

Use a dummy node to simplify head changes. Find the node before left, then reverse the sublist of length (right-left+1).

Invariant: nodes outside the range remain connected and unchanged.

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

• Invariant: nodes outside the range remain connected and unchanged.
• Pointer rewiring preserves all nodes and changes only their order or links.
• Each step maintains list connectivity and the intended invariant.
• When the traversal ends, the list structure matches the required transformation.

Trace (hand walkthrough)

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

Walk:
- sublist positions 2..4 is 2->3->4
- reverse sublist to 4->3->2
- reconnect: 1->4->3->2->5

Pitfalls to avoid

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

Complexity

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

Implementation notes (Go)

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