92. Reverse Linked List II - Detailed Explanation

Problem Statement

Given the head of a singly linked list and two integers left and right where 1 ≤ left ≤ right ≤ n (the list length), reverse the nodes of the list from position left to position right, and return the reversed list.

Examples

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Explanation: Nodes 2→3→4 are reversed to 4→3→2.

Input: head = [5], left = 1, right = 1
Output: [5]
Explanation: Single node, no change.

Input: head = [1,2,3], left = 1, right = 2
Output: [2,1,3]

Constraints

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

Hints

1. Can you copy node values into an array, reverse the subarray, then rebuild the list?
2. How would you reverse a sublist in‑place by re‑linking pointers one by one?
3. Could you use recursion to reverse the first k nodes, then generalize for arbitrary left/right?

Approach 1 – Brute Force via Array

Explanation

Extract all values, reverse the slice from left−1 to right−1, then rebuild the linked list from that array. Easy to implement but uses O(n) extra space.

Step‑by‑step Walkthrough

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

1. Extract → [1,2,3,4,5]
2. Reverse slice indices 1–3 → [1,4,3,2,5]
3. Rebuild list → 1→4→3→2→5

Python Brute Code

Approach 2 – In‑Place Iterative Reversal

Explanation

Perform one‑pass reversal by “head‑insertion” within the sublist. Use a dummy node to simplify edge cases, locate the node before position left, then iteratively take the next node and insert it immediately after the “pre” node.

Step‑by‑step Walkthrough

For 1→2→3→4→5, left=2, right=4:

1. Create dummy→1→2→3→4→5, set pre=dummy, move pre 1 step to node 1.
2. Let start=pre.next (2), then then=start.next (3).
3. Repeat right−left times (2 iterations):
   • Iter 1: detach 3 → link after pre: dummy→1→3→2→4→5; update then=start.next (4)
   • Iter 2: detach 4 → link after pre: dummy→1→4→3→2→5

Return dummy.next → 1→4→3→2→5.

Visual Diagram

dummy→1→2→3→4→5
      ↑pre, start=2, then=3
After first insert:
dummy→1→3→2→4→5
      ↑pre,      start=2, then=4
After second insert:
dummy→1→4→3→2→5

Python Iterative Code