Given the head of a singly linked list, rearrange the nodes so that all nodes at odd positions (1st, 3rd, 5th, ...) come first, followed by all nodes at even positions (2nd, 4th, ...). Positions refer to the original order, not to the values. Inside each group the original relative order is kept. Return the head.
Examples
Input: head = 1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 3 -> 5 -> 2 -> 4
Input: head = 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7
Output: 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4
Constraints
0 <= number of nodes <= 10**4- Target: O(n) time, O(1) extra space, one pass
Goals
- Split one chain into two by alternating links
- Join the two chains without losing the second chain's head