92. Reverse Linked List II
You are given a singly linked list (its node values are handed to you in order as head) together with two 1-based positions left and right, where left <= right. Flip the direction of the sublist that runs from position left through position right, leave everything before and after it untouched, and return the values of the full list after the flip.
For example, reversing positions 2 through 4 of 1 → 2 → 3 → 4 → 5 produces 1 → 4 → 3 → 2 → 5.
The classic interview follow-up: can you rewire the pointers in a single pass, without copying values out?
Example 1:
Input: head = [1, 2, 3, 4, 5], left = 2, right = 4
Output: [1, 4, 3, 2, 5]
Explanation: The window 2 → 3 → 4 flips to 4 → 3 → 2; nodes 1 and 5 stay put.
Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]
Explanation: A window of one node reverses to itself.
Constraints:
- 1 ≤ n ≤ 500 (number of nodes)
- -500 ≤ node value ≤ 500
- 1 ≤ left ≤ right ≤ n
Hints:
Everything interesting happens at the two seams: the node just before position left, and the node at position right. Find the node before the window first — a dummy node in front of the head means it always exists, even when left = 1.
Head insertion reverses the window in one pass: keep `prev` (the node before the window) and `start` (the first node of the window, which will end up last), and right − left times detach the node after `start` and re-insert it right after `prev`.
If pointers feel slippery, first get correct by copying the window's values out, reversing them, and writing them back — then trade it for the one-pass rewiring.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [1, 2, 3, 4, 5], left = 2, right = 4
Expected output: [1, 4, 3, 2, 5]