Odd Even Linked List

Task Scheduler

Linked List Cycle II

Regroup a singly linked list so all odd-positioned nodes come before all even-positioned nodes, preserving relative order within each group.

Given the `head` of a singly linked list, group all nodes at **odd** positions together followed by all nodes at **even** positions, and return the reordered list. Positions are 1-indexed (the head is position 1, which is odd).

You should keep the relative order of the odd-positioned nodes and the relative order of the even-positioned nodes unchanged, and solve it in place in O(1) extra space (not counting the output).

**Input / output**
- Input: `head: ListNode`
- Output: `ListNode`

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

## Constraints
- 0 <= number of nodes <= 10,000
- -1,000,000 <= node value <= 1,000,000

## Follow-up
Can you do it in a single pass, without counting the list's length first?

The key pattern is: walk two interleaved chains (odd and even) simultaneously with a single pass, splicing each node onto its own chain as you go, then reattach the even chain after the odd chain's tail.

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 over the list. Space: O(1) — only a constant number of pointers are used; the existing nodes are relinked in place, not copied.

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 track.