Odd-Even Linked List
Implement oddEvenList
Given the head of a singly linked list, regroup its nodes so every node that started at an odd position (1st, 3rd, 5th, …) comes before every node that started at an even position (2nd, 4th, 6th, …) — each group keeping its own original relative order — and return the new head. The regrouping happens in place; no node's value changes, only the links between them.
Two pointers walking the list together can build both groups in a single pass: one pointer always skips ahead to the next odd-positioned node, the other always skips ahead to the next even-positioned node, and each skip permanently splices that node into its group's chain. Once the even pointer runs out of nodes, every node has landed in exactly one of the two chains, and pointing the odd chain's tail at the remembered start of the even chain joins them into the final list.
Example 1:
Input: head = [4,8,1,6,3]
Output: [4,1,3,8,6]
Example 2:
Input: head = [9,2]
Output: [9,2]
Example 3:
Input: head = [5]
Output: [5]
+ 6 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes in head ≤ 200 - ●
-1000 ≤ node value ≤ 1000 - ●
Positions are counted from 1 — the first node is odd-positioned
head =
[4, 8, 1, 6, 3]