Odd Even Linked List
Understanding the Problem
This is a rearrangement task with one detail that is easy to misread. The problem groups by "odd" and "even" indices, not odd and even values. The first node (index 1) is odd, the second (index 2) is even, and so on. For [1, 2, 3, 4, 5], the odd-positioned nodes are 1, 3, 5 and the even-positioned nodes are 2, 4. The output keeps the original relative order within each group: 1, 3, 5 followed by 2, 4.
The constraint that shapes the solution is doing this in-place. With an array you could index elements directly, but a linked list forces you to rewire next pointers without losing track of any node. The list is two interleaved chains: one through the odd-indexed nodes and one through the even-indexed nodes. Separating those chains and then joining the odd chain's tail to the even chain's head produces the answer.
Key Constraints:
0 <= n <= 10^4→ The list can be empty, so the code must handle a null head and a single-node list as base cases.-10^6 <= Node.val <= 10^6→ Values can be negative, but the algorithm rearranges by position, not value, so the value range is irrelevant.O(1) extra space, O(n) time→ The problem requires constant extra space and linear time. This rules out copying values into an array (O(n) space) and forces an in-place pointer rearrangement.
Approach 1: Collect into Array
Intuition
Extract all node values into an array, rearrange them (odd-indexed first, then even-indexed), and write them back into the same nodes. This avoids pointer manipulation entirely and is a useful warm-up for getting the index logic right.
The cost is O(n) extra space for the array, which violates the problem's constraint. The next approach removes that array, but the rearrangement logic here is the same idea expressed on values instead of pointers.
Algorithm
- Traverse the linked list and store all node values in an array.
- Separate the values into two groups: values at odd positions (index 0, 2, 4, ...) and values at even positions (index 1, 3, 5, ...).
- Create a new array by concatenating the odd-position values followed by the even-position values.
- Walk through the linked list again, overwriting each node's value with the corresponding value from the rearranged array.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We traverse the list twice: once to collect values, once to write them back. Both passes are O(n).
- Space Complexity: O(n). We store all node values in an array, which takes O(n) space.
The values move correctly, but the array costs O(n) space. The next approach rearranges the nodes themselves by editing their next pointers, using only a constant number of extra pointers.
Approach 2: In-Place Pointer Rearrangement
Intuition
The linked list is two interleaved chains: odd-indexed nodes form one chain, even-indexed nodes form another, and they alternate. Splitting them into two separate chains and then connecting the odd chain's tail to the even chain's head produces the result, and the splitting needs no extra memory because it only relinks existing nodes.
Two pointers drive the split. odd starts at the first node (head) and even starts at the second node (head.next). A third pointer, evenHead, saves the start of the even chain so the two chains can be joined at the end.
Walking the list, each step relinks two nodes. odd.next is set to even.next, which is the next odd node, then odd advances onto it. even.next is then set to the new odd.next, which is the next even node, then even advances onto it. When even or even.next becomes null, every node has been placed in its chain, and odd.next = evenHead joins the two.
Two invariants hold at the start of every iteration: odd is the current tail of the odd chain, and even is the current tail of the even chain. Each iteration extends both chains by one node and re-establishes the invariants, so after the loop the odd chain holds every odd-indexed node in order and the even chain holds every even-indexed node in order.
The loop condition even != null && even.next != null covers both list lengths. With an odd number of nodes, even reaches null after the last even node is placed; with an even number of nodes, even.next is null because even sits on the final node. In both cases every node is placed before odd.next = evenHead runs, and the original odd.next and even.next links are overwritten before they are read, so no node is lost or duplicated.
Algorithm
- If the list is empty or has only one node, return it as-is.
- Initialize
odd = headandeven = head.next. SaveevenHead = even. - While
even != nullandeven.next != null: - Set
odd.next = even.next(link to the next odd node). - Advance
odd = odd.next. - Set
even.next = odd.next(link to the next even node). - Advance
even = even.next. - Connect the odd chain to the even chain:
odd.next = evenHead. - Return
head.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We traverse each node exactly once. Each iteration processes two nodes (one odd, one even), so the loop runs n/2 times.
- Space Complexity: O(1). We only use three extra pointers (
odd,even,evenHead) regardless of the input size.