Reverse Linked List II

Swap Nodes in Pairs

Convert Sorted Array to Binary Search Tree

Reverse only the nodes between two 1-indexed positions of a singly linked list, in one pass.

Given the `head` of a singly linked list and two integers `left` and `right` (1-indexed, `left <= right`), reverse the nodes from position `left` to position `right`, then return the head of the modified list.

**Input / output**
- Input: `head: ListNode`, `left: int`, `right: int` (JSON test fixture for `head` is a plain array of node values, e.g. `[1, 2, 3, 4, 5]` means `1 -> 2 -> 3 -> 4 -> 5 -> null`)
- Output: `ListNode` (serialized the same way)

## Example
```json
Input: {"head":[1,2,3,4,5],"left":2,"right":4}
Output: [1,4,3,2,5]
```

## Constraints
- The number of nodes in the list is between 1 and 500.
- `-500 <= node value <= 500`
- `1 <= left <= right <= number of nodes`

## Follow-up
Can you do it in a single pass through the list, without ever counting the length or making a second traversal?

The key pattern is: a dummy-node walk to the node just before `left`, then repeatedly splicing the next node to the front of the reversed segment. Identify the state and invariant before coding.

Recognize the Pattern

Advance one state transition at a time. Mark or update state before exploring dependent work.

Build the Algorithm

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

Check Edge Cases

Time: O(n) — a single pass to reach `left` plus one pass to reverse the segment. Space: O(1) auxiliary in Python/JavaScript/Java/Go, which splice pointers in place. The Rust implementation instead collects values into a `Vec` and rebuilds the list (O(n) auxiliary) because the classic pointer splice runs into move/borrow conflicts on `Option<Box<ListNode>>` chains — see the inline comment on the Rust solution.

All 5 languages below run and submit against the remote judge for this problem — Java/Go/Rust use the same real ListNode structural-type support the judge added for the rest of the linked-list/tree track.