Relink Odd Positions before Even Positions Stably
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Reorder the original singly linked nodes so positions 1,3,5,... come first, followed by positions 2,4,6,... . Preserve relative order within each group. Positions are one-based; parity is based on position, not node value. Return the reordered ListNode* head in O(n) time and O(1) extra space.
```cpp
ListNode* oddEvenList(ListNode* head);
```
### Examples
```text
head = [8,3,6,1,4] -> [8,6,4,3,1]
head = [] -> []
```
### Constraints
- There are 0 through 10000 nodes.
- Values lie in [-1000000,1000000].
Overview: Relink Odd Positions before Even Positions Stably. Reorder the original singly linked nodes so positions 1,3,5,... come first, followed by positions 2,4,6,... . Preserve relative order within each group. Positio
