Odd Even Linked List solution and explanation
Google
Infosys
TCS
9 more videos on this problem
L6. Odd Even Linked List | Multiple Approachestake U forward · 24:05 · 279K views
LeetCode Odd Even Linked List Solution Explained - JavaNick White · 6:18 · 57K views
Odd Even Linked List | Leetcode #328 | Segregate odd even inplaceTechdose · 11:48 · 46K views
Odd Even Linked List (LeetCode 328) | Full solution with diagrams | Study AlgorithmsNikhil Lohia · 15:38 · 23K views
Leetcode - Odd Even Linked List (Python)Timothy H Chang · 7:15 · 7K views
Odd Even Linked List | LeetCode 328 | Coding Interview TutorialTerrible Whiteboard · 10:02 · 4K views
LeetCode 328. Odd Even Linked List [Algorithm + Code Explained ]jayati tiwari · 11:30 · 4K views
Odd Even Linked List - LeetCode 328 - Python #leetcode #leetcode75Deepti Talesra · 6:20 · 4K views
LeetCode 328: Odd Even Linked ListEngineering Digest · 6:38 · 2K views
ODD EVEN LINKED LIST | LEETCODE # 328 | PYTHON SOLUTIONCracking FAANG · 9:01 · 2K views
The problem
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:
- The number of nodes in the linked list is in the range
[0, 104]. -106 <= Node.val <= 106
Approach overview
Problem 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 1: Two Pointers Approach
This approach uses two pointers to manage odd and even indexed nodes separately. We maintain separate pointers for the head of the odd and even lists and iterate through the given list. As we go along, we link odd indices to the next odd and even indices to the next even. In the end, we connect the last odd indexed node to the head of the even indexed list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
odd = head
even = head.next
evenHead = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = evenHead
return headclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* odd = head;
ListNode* even = head->next;
ListNode* evenHead = even;
while (even && even->next) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}
};function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
function oddEvenList(head) {
if (head === null || head.next === null) return head;
let odd = head;
let even = head.next;
let evenHead = even;
while (even !== null && even.next !== null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* oddEvenList(struct ListNode* head) {
if (!head || !head->next) return head;
struct ListNode* odd = head;
struct ListNode* even = head->next;
struct ListNode* evenHead = even;
while (even && even->next) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode OddEvenList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}Initially, the function checks if the list is empty or a single node exists. 'odd' and 'even' pointers are initialized, with another pointer 'evenHead' remembering the even list's start. The loop iterates through nodes, connecting odd nodes and even nodes separately. In the end, the sequence of odd nodes is merged with the even section.
The solution has a Time Complexity of O(n) due to one complete traversal of the list. Space Complexity is O(1) as restructuring happens in-situ.
Approach 2: Recursive Approach
Although not typical due to O(1) space requirement, this problem could conceptually be solved recursively by defining a function that processes the head and its next elements recursively, managing pointers for odd and even segments. As recursion inherently uses extra space on the stack, this isn't space-optimal, thus academically interesting but not compliable with constant space constraints.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
def partition(node, is_odd):
if not node or not node.next:
return None, node
next_part = partition(node.next, not is_odd)[0 if is_odd else 1]
node.next = next_part
return node if is_odd else node.next, node if not is_odd else node.next
if not head: return None
odd, even = partition(head, True)
if odd: odd.next = even
return headThis Python solution uses a local function 'partition' which recursively treats nodes as alternating odd or even. Despite functional recursion achieving the same odd-even connection, it ruins constant space by occupying stack memory, which might exceed constraints under deep recursion.
Time Complexity remains O(n) for full list traversal. However, Space Complexity rises to O(n) because of the call stack in recursion, unsuitable under given problem constraints for constant space.
Approach 3: Single Pass
We can use two pointers a and b to represent the tail nodes of the odd and even nodes respectively. Initially, pointer a points to the head node head of the list, and pointer b points to the second node head.next of the list. In addition, we use a pointer c to point to the head node head.next of the even nodes, which is the initial position of pointer b.
We traverse the list, set pointer a to point to the next node of b, i.e., a.next = b.next, then move pointer a back by one position, i.e., a = a.next; set pointer b to point to the next node of a, i.e., b.next = a.next, then move pointer b back by one position, i.e., b = b.next. Continue to traverse until b reaches the end of the list.
Finally, we set the tail node a of the odd nodes to point to the head node c of the even nodes, i.e., a.next = c, then return the head node head of the list.
The time complexity is O(n), where n is the length of the list, and we need to traverse the list once. The space complexity is O(1). We only need to maintain a limited number of pointers.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function oddEvenList(head: ListNode | null): ListNode | null {
if (!head) {
return null;
}
let [a, b, c] = [head, head.next, head.next];
while (b && b.next) {
a.next = b.next;
a = a.next;
b.next = a.next;
b = b.next;
}
a.next = c;
return head;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func oddEvenList(head *ListNode) *ListNode {
if head == nil {
return nil
}
a := head
b, c := head.Next, head.Next
for b != nil && b.Next != nil {
a.Next = b.Next
a = a.Next
b.Next = a.Next
b = b.Next
}
a.Next = c
return head
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointers Approach | The solution has a Time Complexity of O(n) due to one complete traversal of the list. Space Complexity is O(1) as restructuring happens in-situ. |
| Recursive Approach | Time Complexity remains O(n) for full list traversal. However, Space Complexity rises to O(n) because of the call stack in recursion, unsuitable under given problem constraints for constant space. |
| Single Pass | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Odd Even Linked List easy or hard?
Odd Even Linked List is typically rated Medium difficulty. The logic is simple once understood, but many candidates make mistakes updating pointers or lose track of the even list head during traversal.
Odd Even Linked List Python/Java solution
Most implementations follow the same logic across languages: maintain odd, even, and evenHead pointers, iterate through the list, and reconnect pointers. The approach works identically in Python, Java, C++, C#, and JavaScript because it relies only on pointer references.
How to solve Odd Even Linked List in O(n)?
Traverse the linked list using two pointers: one tracking odd-position nodes and another tracking even-position nodes. Rewire pointers so odd nodes skip over even ones and even nodes skip over odd ones. After traversal, connect the last odd node to the head of the even list.
What is the best approach for Odd Even Linked List?
The two pointers approach is the most efficient and commonly expected solution. It separates the list into odd and even position chains while traversing once, then attaches the even list after the odd list. This runs in O(n) time with O(1) extra space because the rearrangement is done in-place.
Is Odd Even Linked List asked at Google/Amazon/Meta?
Odd Even Linked List frequently appears in interviews at companies that emphasize pointer manipulation and linked list fundamentals, including Amazon and Meta-style interview sets. It tests in-place list restructuring and careful pointer updates.
What data structure is used in Odd Even Linked List?
The problem uses a singly linked list. The solution focuses on pointer manipulation—specifically updating the next references of nodes to reorder them without allocating additional data structures.
What is the time complexity of Odd Even Linked List?
The optimal solution runs in O(n) time because each node is visited exactly once while updating next pointers. Space complexity is O(1) since the algorithm only maintains a few pointers such as odd, even, and evenHead.