Reorder a singly linked list so that all nodes at odd indices appear before all nodes at even indices, while preserving the relative order within each group.
Given the head of a singly linked list, rearrange the nodes so that all nodes in odd positions come first, followed by all nodes in even positions.
The position of the first node is considered odd, the second node even, the third odd, and so on. You must keep the original relative order among the odd-positioned nodes and among the even-positioned nodes.
Do this by rewiring pointers in the linked list, not by creating a new list of node values.
Input Format
- A singly linked list head.
- Nodes contain integer values.
- Positions are 1-indexed from the head.
Output Format
- Return the head of the reordered linked list.
Constraints
- The list may be empty or contain a single node.
- Preserve the relative order of nodes within odd and even positions.
- Aim for time and extra space.
Example 1
Input
head = [1,2,3,4,5]
Output
[1,3,5,2,4]
Explanation
Odd-position nodes are 1, 3, 5 and even-position nodes are 2, 4. The final list keeps each group in order.
Example 2
Input
head = [2,1,3,5,6,4,7]
Output
[2,3,6,7,1,5,4]
Explanation
Nodes at odd positions are [2,3,6,7] and nodes at even positions are [1,5,4].
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.