279. Odd Even Linked List
You are given head, the first node of a singly linked list. Rearrange the list in place so that all nodes sitting at odd positions (the 1st, 3rd, 5th, … node) come first, followed by all nodes at even positions (the 2nd, 4th, 6th, …), and return the head of the rearranged list.
Grouping is decided by a node's position in the list, never by the value it stores. Within each group, nodes must keep the relative order they had in the original list.
Your solution must run in O(n) time and use only O(1) extra space — rewiring pointers, not copying nodes.
Example 1:
Input: head = [1, 2, 3, 4, 5]
Output: [1, 3, 5, 2, 4]
Explanation: Positions 1, 3, 5 hold the values 1, 3, 5 and move to the front; positions 2 and 4 hold 2 and 4 and follow, each group keeping its original order.
Example 2:
Input: head = [2, 1, 3, 5, 6, 4, 7]
Output: [2, 3, 6, 7, 1, 5, 4]
Explanation: The odd positions (1st, 3rd, 5th, 7th) carry 2, 3, 6, 7; the even positions (2nd, 4th, 6th) carry 1, 5, 4. Note the grouping ignores whether the values themselves are odd or even.
Constraints:
- 0 ≤ number of nodes ≤ 10⁴
- -10⁶ ≤ Node.val ≤ 10⁶
- Required: O(n) time and O(1) extra space.
Hints:
Think of the list as two interleaved chains: the odd-position nodes and the even-position nodes. Can you unzip them in one pass?
Keep two runners, `odd` and `even`, plus a saved `evenHead`. Each step: `odd.next = even.next`, advance `odd`; then `even.next = odd.next`, advance `even`.
When the walk ends, the odd chain's tail is `odd` — attach the saved `evenHead` there. Check `even` before `even.next` in the loop condition to survive both parities of length.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [1, 2, 3, 4, 5]
Expected output: [1, 3, 5, 2, 4]