Community Problem
Odd Even Linked List
Difficulty: Medium
Reorder a singly-linked list so all odd-positioned nodes come before even-positioned ones, in O(n) time and O(1) space using two interleaved sub-lists.
Odd Even Linked List
Reorder a singly-linked list so all odd-positioned nodes come before even-positioned ones, in O(n) time and O(1) space using two interleaved sub-lists.
By @nehawood
March 27, 2026
·
Updated May 18, 2026
512 views
3
4.5 (13)
I keep this one in my linked-list rotation because the obvious approach (build two new lists with new nodes) misses the constraint: in-place pointer rewiring with no new allocations. The clean version uses just four pointers (oddHead, oddTail, evenHead, evenTail) and a single pass.
Odd Even Linked List
Given the head of a singly-linked list, group all nodes at odd positions (the 1st, 3rd, 5th, ...) followed by all nodes at even positions (the 2nd, 4th, 6th, ...) and return the reordered head. Position is by index in the input list, not by node value. Relative order within each group must be preserved.
The reordering must be done in O(n) time and O(1) extra space (i.e. by re-pointing existing nodes, not by allocating new ones).
Examples
Example 1:
- Input:
head = [1, 2, 3, 4, 5] - Output:
[1, 3, 5, 2, 4] - Explanation: Odd positions (1st, 3rd, 5th) hold values
1, 3, 5. Even positions (2nd, 4th) hold values2, 4. Concatenate.
Example 2:
- Input:
head = [2, 1, 3, 5, 6, 4, 7] - Output:
[2, 3, 6, 7, 1, 5, 4] - Explanation: Odd positions hold
2, 3, 6, 7. Even positions hold1, 5, 4.
Example 3:
- Input:
head = [1] - Output:
[1] - Explanation: Single node.
Example 4:
- Input:
head = [] - Output:
[] - Explanation: Empty list.
Constraints
- The number of nodes in the list is in the range
[0, 10^4]. -10^6 <= Node.val <= 10^6
Solution
Hints
Approach
Maintain two pointers that act as the tails of two interleaved sub-lists: odd for odd positions (1st, 3rd, 5th, ...) and even for even positions (2nd, 4th, 6th, ...). Start with odd = head, even = head.next. Each iteration steals the next two nodes (one for odd, one for even) and appends them to the respective sub-list tail. After the scan, splice the even sub-list onto the tail of the odd sub-list.
Key insight
Because we are weaving from a single shared source list, both sub-lists grow synchronously. The trick is that odd.next always points to the next ODD-position node (after re-pointing), and even.next always points to the next EVEN-position node, which means we never need lookups beyond two hops. The terminating condition is even !== null && even.next !== null, which covers both the odd-length and even-length termination cleanly.
Algorithm
- Edge cases: if
headis null or has only one node, return as-is. - Initialize
odd = head,even = head.next,evenHead = even. - While
even !== null && even.next !== null:odd.next = even.next(skip over the even node).odd = odd.next(advance odd tail).even.next = odd.next(skip over the new odd-tail's neighbor).even = even.next(advance even tail).
- Splice:
odd.next = evenHead. - Return
head.
Complexity
Metric Value
------ -----
Time O(n)
Space O(1) auxiliaryA single linear pass; we re-point existing pointers in place.
Why it works
The loop invariant is: odd is the current tail of the odd sub-list, even is the current tail of the even sub-list, and the unprocessed remainder of the input list still hangs off even.next. Each iteration consumes the next two unprocessed nodes (an odd one and an even one) and appends them to their sub-list tails, preserving the invariant. The termination condition guarantees even.next is non-null at the start of each iteration, so the four pointer assignments are always safe.
Pitfalls
- Loop condition: using
odd.next !== nullinstead ofeven !== null && even.next !== nullover-runs the even-length case. Always testeven(which is the trailing of the two pointers). - Forgetting
evenHeadand trying to find the head of the even sub-list at the end. Save it once at the top. - Confusing position with value parity. The problem is by INDEX, not by VALUE.
- Sandpack
for...ofon Maps would break, but we're using plain pointer walks here, so no issue.
Solution Code