Odd Even Linked List
Odd Even Linked List: group nodes at odd positions before nodes at even positions, preserving relative order.
- The number of nodes in the linked list is in the range [0, 10⁴].
- -10⁶ <= Node.val <= 10⁶
Intuition
Odd even linked list regroups a list so all nodes in odd positions come first, followed by all nodes in even positions. Positions are counted by index, not by node value — a distinction the name obscures and which catches many first attempts.
The requirements are O(1) space and O(n) time, so the nodes must be relinked in place rather than collected into lists.
The technique is to weave two chains through the original list simultaneously:
- Maintain an odd pointer and an even pointer, each advancing two nodes at a time, so each builds its own chain in a single pass.
Since every node's successor's successor shares its parity, odd.next = even.next and even.next = odd.next step each chain forward correctly.
Saving the head of the even chain before the loop is essential — it is needed at the end to join the two chains, and by then the even pointer has moved to the chain's tail.
The loop condition must be even && even.next. Checking only even dereferences null when the list has an odd number of nodes, and checking only odd misses the case where the even chain is already exhausted.
After the loop, odd.next = evenHead joins the chains. Omitting that step leaves the odd chain terminated and silently discards every even-positioned node.
The relative order within each group must be preserved, which this approach gives for free since nodes are visited in their original sequence.
Empty lists and single-node lists need no work — the loop condition fails immediately and the head is returned unchanged.
Weave two chains through the original list in a single pass, then join them. Saving even_head before the weaving starts is essential — it's the only reference to the second chain once the pointers have moved.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(1) space.
Read positions, not values
Odd and even refer to a node's index, not its value. The first node is position 1, and misreading this is the most common first mistake.
Weave two chains at once
Keep an odd pointer and an even pointer, advancing each two nodes at a time. Every node's successor's successor shares its parity, so each chain builds correctly.
Save the even head first
Store the second node before the loop begins. It is needed to join the chains at the end, by which time the even pointer sits at the tail.
Guard the loop correctly
Loop while even && even.next. Checking only even dereferences null on odd-length lists, and checking only odd misses an exhausted even chain.
Join the chains
Set odd.next = evenHead after the loop. Omitting this leaves the odd chain terminated and silently discards every even-positioned node.
Preserve relative order
Nodes are visited in their original sequence, so the order within each group is preserved automatically with no extra work.
Cost of the approach
One pass relinking pointers gives O(n) time and O(1) space, meeting both stated requirements.
Solution & live demo
Common pitfalls
Not saving the even head
odd = head even = head.next # weave, then odd.next = even
even_head = even # weave, then odd.next = even_head
By the end of the loop even points at the last even node, not the first. Linking to it creates a one-node tail and loses the rest of the even chain.
Relinking in the wrong order
even.next = odd.next odd.next = even.next
odd.next = even.next odd = odd.next even.next = odd.next even = even.next
Each assignment must read a pointer the previous one hasn't yet overwritten. Reversing them makes odd.next read the value just written, folding the list onto itself.
Getting the loop condition wrong
while even:
while even and even.next:
The body dereferences even.next to advance the odd chain. With an even-length list even.next is null on the last iteration and the loop throws.
Edge cases
Already grouped; return head unchanged.
The even chain ends naturally at the last node.
The odd chain gains the final node; even terminates before it.
Return None before touching any pointer.