Given the head of a singly linked list, regroup it so that every node in an odd position comes first, followed by every node in an even position. Position is counted from 1: the first node is odd, the second is even, the third is odd, and so on — this is about a node's place in the list, not the value stored in it.
Within each group the nodes must keep their original relative order. Return the head of the regrouped list.
You must do this using only O(1) extra space and O(n) time — rewire the existing nodes, don't build a copy.
next pointers you already have.node.next.next).node.val. The first node is odd, the second even, regardless of the numbers stored.odd pointing at the last odd node; to finish you attach the whole even chain with odd.next = evenHead. Without saving it, you'd have no handle on the start of the even chain.even always trails odd by one node, so even (and even.next) become null first. Checking even and even.next guarantees every pointer you dereference exists.node.val % 2; the relinking logic is identical.i % k, then chain the k sublists together in order.Input: head = [1,2,3,4,5] Output: [1,3,5,2,4] Odd positions 1,3,5 hold 1,3,5; even positions 2,4 hold 2,4. Odd group first, then even group.
Input: head = [2,1,3,5,6,4,7] Output: [2,3,6,7,1,5,4] Odd positions hold 2,3,6,7; even positions hold 1,5,4. Concatenate odd then even.
- The number of nodes in the list is in the range [0, 10^4]. - -10^6 <= Node.val <= 10^6
Regrouping a linked list by position sounds like it needs scratch space — but the whole point here is to rewire the nodes you already have. Let's build up from the obvious copy-it-out approach to the in-place weave the interviewer is really after.
node = node.next loop until you hit null.next to splice it elsewhere without allocating new nodes.1, so the first node is odd and the second is even.In plain words: keep every node, but reorder them so all position-odd nodes come first (in their original order), then all position-even nodes (in their original order). Position is 1-indexed and has nothing to do with the value stored in a node.
Worked example — head = [1,2,3,4,5]
positions: 1 2 3 4 5 head: 1 → 2 → 3 → 4 → 5 odd (pos 1,3,5): 1 → 3 → 5 even (pos 2,4): 2 → 4 join even after odd: 1 → 3 → 5 → 2 → 4
Naming your assumptions before you code is what separates a senior candidate from someone who dives in and backtracks.
“Does odd and even mean the node position or the node value?”
Position, 1-indexed. Confirming this stops you from accidentally grouping by node.val parity.
“What should I return for an empty list or a single node?”
Both are already grouped — return the head unchanged. These guard the loop setup.
“Is there a hard limit on extra space?”
Yes — O(1) extra space, so copying values into arrays is off the table for the intended answer.
Before I start, a couple of quick clarifications.
By odd and even we mean the node's position in the list, one-indexed, not its value — correct?
And I should treat an empty or single-node list as already grouped, returning it as-is.
As you walk the list, parity strictly alternates. So from any odd node, the next odd node is its next.next; from any even node, the next even node is its next.next. That means you never need a position counter — the structure already tells you.
1 → 2 → 3 → 4 → 5
\_______/ odd 1's next odd is 3 (two hops)
\_______/ even 2's next even is 4Keep an odd pointer (tail of the odd chain) and an even pointer (tail of the even chain). Then odd.next = even.next pulls the next odd node forward, and even.next = odd.next pulls the next even node forward. Advance both and repeat — the two chains grow simultaneously out of the original nodes.
The loop ends with odd at the last odd node and the even chain dangling separately. To reattach it you need its first node, so capture evenHead = head.next before the loop and finish with odd.next = evenHead.
| Brute force | Optimal | |
|---|---|---|
| Idea | Copy values into two arrays, write back | Weave two chains via pointers |
| Time | O(n) | O(n) |
| Space | O(n) | O(1) |
Both run in linear time, but only the pointer weave meets the required O(1) extra space. See the full code for each in the Approaches selector below.
Key takeaway
When a problem says regroup nodes in place, reach for multiple tail pointers that weave the existing nodes instead of copying data. Grow the sub-chains together, then stitch them end to end.
if list has 0 or 1 node: return head
odd, even = head, head.next
evenHead = even
while even and even.next:
odd.next = even.next; odd = odd.next
even.next = odd.next; even = even.next
odd.next = evenHead
return head