Loading...
Loading...
You are given head, the first node of a singly linked list. Number the nodes by position starting at 1, so the first node is at position 1, the second at position 2, and so on.
Rearrange the list so that every node at an odd position comes before every node at an even position. Within each group, keep the nodes in their original relative order.
Return the head of the rearranged list.
You must solve this using O(1) extra space and O(n) time.
Your function receives head as a ListNode (or null for the empty list) and returns the head of the rearranged list. The node type is provided for you, with val and next fields; you may relink the existing nodes in place.
The examples below write a list as the array of its values in order, so [1,2,3] is the list 1 -> 2 -> 3. That is only how lists are displayed; the encoding and decoding are done for you.
The odd-position chain, then the even-position chain.
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
Explanation: Positions 1, 3, 5 hold values 1, 3, 5. Positions 2, 4 hold values 2, 4. Placing the odd-position values first gives 1, 3, 5, 2, 4.
Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]
Explanation: Positions 1, 3, 5, 7 hold values 2, 3, 6, 7. Positions 2, 4, 6 hold values 1, 5, 4. Placing the odd-position values first gives 2, 3, 6, 7, 1, 5, 4.
Node.val ≤106