Odd Even Linked List — Solution in Python, Java & C++
Odd Even Linked List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on two pointers.
Odd Even Linked List is a medium coding problem on two pointers, asked in Amazon, Microsoft, Adobe and Bloomberg interviews.
- Difficulty: Medium
- Topics: Two Pointers
- Asked at: Amazon, Microsoft, Adobe, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the head of a singly linked list, group all the nodes at odd positions first, followed by the nodes at even positions, and return the head of the reordered list. Positions count from 1, so the head is odd and the second node even — this is about positions, not values.
Keep the relative order inside each group. Use O(1) extra space and O(n) time.
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]
Explanation: Positions 1, 3, 5, 7 hold 2, 3, 6, 7; positions 2, 4, 6 hold 1, 5, 4.
Example 3
Input: head = []
Output: []
Constraints
The number of nodes in the list is in the range [0, 10^4]-10^6 <= Node.val <= 10^6
Hints for Odd Even Linked List
Hint 1
Think of the list as two interleaved lists: odd positions and even positions.
Hint 2
Walk with two pointers,
oddandeven, each skipping over the other:odd.next = even.next, theneven.next = odd.next.Hint 3
Remember the head of the even chain before you start, and attach it after the last odd node at the end.
How to solve Odd Even Linked List
Unzip the list into its odd-position chain and its even-position chain in one pass by letting each pointer jump over the other, then join the even chain after the odd one.
Approach
- If the list is empty, return it. Set
odd = head,even = head.next,evenHead = even. - While
evenandeven.nextexist:odd.next = even.next;odd = odd.next;even.next = odd.next;even = even.next. - Link
odd.next = evenHeadand returnhead.
Why it works
Each step links an odd node to the next odd node (two ahead) and an even node to the next even node, so the two chains keep their original orders. The loop stops when no odd node remains after even, and at that point odd is the last odd-position node, where the even chain belongs.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Positions, not values: an even value at position 1 still goes first.
- Save
evenHeadbefore relinking —head.nextwill no longer point at it. - The loop condition must check
evenandeven.nextsooddnever becomes null.
Reference solution
Python
from typing import Optional
def oddEvenList(head: Optional[ListNode]) -> Optional[ListNode]:
if head is None:
return head
odd, even = head, head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return headJava
public static ListNode oddEvenList(ListNode head) {
if (head == null) return head;
ListNode odd = head, even = head.next, 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;
}C++
ListNode* oddEvenList(ListNode* head) {
if (!head) return head;
ListNode *odd = head, *even = head->next, *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;
}JavaScript
var oddEvenList = function(head) {
if (head === null) return head;
var odd = head, even = head.next, 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;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 165 two pointers problems · the whole catalogue
Learn the technique: Two Pointers Technique