You are given a singly linked list. Count the positions starting from 1, so the first node is at position 1 (odd), the second at position 2 (even), and so on.
Rearrange the list so that all nodes at odd positions come first, followed by all nodes at even positions. Inside each of the two groups, the nodes must stay in their old order. Return the new list.
Your solution must use O(1) extra space and O(n) time.
How the judge passes the data
Examples
Example 1:
Input: head = [10,20,30,40,50,60]
Output: [10,30,50,20,40,60]
Explanation: Positions 1, 3, 5 hold 10, 30, 50. Positions 2, 4, 6 hold 20, 40, 60.
Example 2:
Input: head = [7,3,9]
Output: [7,9,3]
Explanation: Positions 1 and 3 come first (7, 9). Position 2 (3) goes after them.
Example 3:
Input: head = [5]
Output: [5]
Explanation: A list with one node does not change.