323. Odd Then Even Links
A parade is lined up as a chain of floats numbered by position, with the first float at position 1. The organiser wants every float in an odd position to lead the parade, followed by every float in an even position, while the floats inside each group keep the same order they had before.
Given the head of the chain, regroup the nodes in this way and return the head of the new chain. The decision depends only on the position in the original chain (1st, 2nd, 3rd, ...), never on the stored values, which may be repeated or negative. Rearrange the existing nodes by changing their links, using only constant extra memory. The chain may be empty and can hold up to 100,000 floats.
Example 1
- Input:
- head = [10,20,30,40,50,60,70]
- Output:
- [10,30,50,70,20,40,60]
- Explanation:
Positions 1, 3, 5, 7 hold 10, 30, 50, 70 and positions 2, 4, 6 hold 20, 40, 60, giving 10, 30, 50, 70, 20, 40, 60.
Example 2
- Input:
- head = [8,8,3,3]
- Output:
- [8,3,8,3]
- Explanation:
Positions 1 and 3 hold 8 and 3; positions 2 and 4 hold 8 and 3; the result is 8, 3, 8, 3.
Constraints
0 ≤ chain length ≤ 105
-105 ≤ node value ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)