Odd Even Linked List
Move every node at an odd position ahead of the nodes at even positions, in place, by growing an odd chain and an even chain and joining them.
Problem Understanding
Odd Even Linked List (LeetCode 328): given the head of a singly linked list, group all nodes at odd positions together, followed by the nodes at even positions, and return the reordered list. The first node is position 1 (odd). Keep the relative order inside each group, and use O(1) extra space and O(n) time.
Examples: [1, 2, 3, 4, 5] → [1, 3, 5, 2, 4]; [2, 1, 3, 5, 6, 4, 7] → [2, 3, 6, 7, 1, 5, 4].
The Intuition: Two Chains Leapfrog
Odd and even nodes alternate, so every odd node's next odd node is two steps away, and the same for even nodes.
- Start two chains. The odd chain at head, the even chain at head.next. Save the start of the even chain.
- Leapfrog. Point the odd tail past the even tail to the next odd node, then the even tail past that to the next even node.
- Join. When the even chain cannot grow, hang it off the end of the odd chain.
Relinking pointers in place instead of copying values is the same skill as Reverse Linked List and Swap Nodes in Pairs.
Interactive Walkthrough
RELINK IN PLACE · O(1) SPACE
SPLIT AT HEAD
odd chain
odd
0
…
even chain
even
1
…
odd
1
even
2
evenHead
2
odd = head (1), even = head.next (2). Remember evenHead = 2
Next
odd.next = even.next: 1 now points past 2 to 3, the next odd node
head
The two rows are the two chains in link order; the small number under a node is its index in the input. odd is filled and even outlined. Try Even length to see the loop stop with even on the last node.
Dry Run Table
Input: [1, 2, 3, 4, 5], evenHead = 2.
| Step | Change | Odd chain | Even chain |
|---|---|---|---|
| start | odd = 1, even = 2 | 1 | 2 |
| 1 | 1.next = 3 | 1 → 3 | 2 |
| 2 | 2.next = 4 | 1 → 3 | 2 → 4 |
| 3 | 3.next = 5 | 1 → 3 → 5 | 2 → 4 |
| 4 | 4.next = NULL | 1 → 3 → 5 | 2 → 4 |
| join | 5.next = 2 | 1 → 3 → 5 → 2 → 4 |
Answer: [1, 3, 5, 2, 4].
The Solution Template
Two tail pointers that leapfrog each other, a saved evenHead, and one join at the end.
Odd Even Linked List Code
1var oddEvenList = function(head) {2 if (!head) {3 return head;4 }5 let odd = head, even = head.next;6 const evenHead = even;7 while (even && even.next) {8 odd.next = even.next;9 odd = odd.next;10 even.next = odd.next;11 even = even.next;12 }13 odd.next = evenHead;14 return head;15};
Edge Cases & Common Mistakes
- Empty list: return head (null) before touching head.next.
- One or two nodes: the loop does not run and the list is already in order.
- Forgetting evenHead: without it the even chain is unreachable at the join.
- Grouping by value: the problem is about positions, not whether the values are odd.
- Cutting the even chain off: the last even node's next must end up null, which the loop's
even.next = odd.nextguarantees on an odd-length list.
Summary
Keep tails for an odd chain and an even chain, leapfrog them along the list, and join the odd tail to the saved evenHead. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet