Description
Given the head of a singly linked list, group all odd-indexed nodes together followed by the even-indexed nodes, and return the reordered list. The first node is index 1 (odd), the second is index 2 (even), etc. You must solve the problem in O(1) extra space complexity and O(n) time complexity.
Examples
Input:
head = [1,2,3,4,5]Output:
[1,3,5,2,4]Explanation:
Odd indices: 1,3,5. Even indices: 2,4.
Input:
head = [2,1,3,5,6,4,7]Output:
[2,3,6,7,1,5,4]Explanation:
Odd indexed nodes grouped, then even indexed nodes.
Input:
head = [8,15,-3,22]Output:
[8,-3,15,22]Explanation:
With 4 nodes: odd indices are positions 1 and 3 (values 8, -3), even indices are positions 2 and 4 (values 15, 22). The reordered list groups odd-indexed nodes first [8,-3] followed by even-indexed nodes [15,22].
Constraints
- •
The number of nodes is in the range [0, 10⁴]. - •
-10⁶ ≤ Node.val ≤ 10⁶