Watch 10 video solutions for Odd Even Linked List, a medium level problem involving Linked List. This walkthrough by take U forward has 250,617 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.
The first node is considered odd, and the second node is even, and so on.
Note that the relative order inside both the even and odd groups should remain as it was in the input.
You must solve the problem in O(1) extra space complexity and O(n) time complexity.
Example 1:
Input: head = [1,2,3,4,5] Output: [1,3,5,2,4]
Example 2:
Input: head = [2,1,3,5,6,4,7] Output: [2,3,6,7,1,5,4]
Constraints:
[0, 104].-106 <= Node.val <= 106Problem Overview: Rearrange a singly linked list so that nodes at odd indices appear first, followed by nodes at even indices. The relative order inside the odd group and even group must stay the same. Indexing is based on node position in the list, not the node values.
Approach 1: Two Pointers (O(n) time, O(1) space)
The optimal solution splits the list into two chains while traversing it once. Maintain two pointers: odd for nodes at odd positions and even for nodes at even positions. Also keep a reference to the head of the even list (evenHead) so it can be attached after the odd sequence at the end. During iteration, update pointers by skipping alternating nodes: odd.next = even.next and even.next = odd.next. This effectively builds two sublists in-place without extra memory. When traversal finishes, connect the last odd node to evenHead. The list is rearranged in a single pass with constant extra space, which makes this the expected interview solution when working with linked list pointer manipulation.
The key insight is that nodes do not need to be reordered individually; instead, the existing next pointers are rewired to group odd and even positions. Since every node is visited once, the runtime stays linear. This pattern—maintaining two moving references while rewiring pointers—is common in problems involving two pointers on linked structures.
Approach 2: Recursive Re-linking (O(n) time, O(n) space)
A recursive approach processes the list in pairs and rebuilds the odd and even sequences during the recursion stack unwinding. At each recursive step, treat the current node as an odd node and its next node as an even node. Recursively process the rest of the list starting from head.next.next. The recursive call returns the reorganized list of remaining nodes, which is then attached to maintain the odd-first ordering.
This method expresses the problem more declaratively: each call handles a small segment and delegates the remainder of the list to recursion. However, recursion consumes stack space proportional to the number of nodes, leading to O(n) auxiliary space. Pointer-heavy linked list problems rarely benefit from recursion in production code, but it can help illustrate how the list structure evolves step by step. It also reinforces understanding of pointer references and structural decomposition commonly seen in recursion-based linked list problems.
Recommended for interviews: The two pointers approach is the expected answer. It runs in O(n) time and O(1) space while modifying the list in-place. Interviewers look for correct pointer updates and careful handling of the even list head. The recursive approach demonstrates conceptual understanding but is rarely preferred because of the additional stack usage.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers | O(n) | O(1) | Best general solution. Rearranges nodes in-place with one traversal. |
| Recursive Re-linking | O(n) | O(n) | Useful for conceptual understanding of linked list restructuring using recursion. |