98. Odd Even Linked List
🔗 LeetCode Problem: 328. Odd Even Linked List
📊 Difficulty: Medium
🏷️ Topics: Linked List
Problem Statement
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]
Visual:
Original: 1 → 2 → 3 → 4 → 5 → null
↑ ↑ ↑ ↑ ↑
odd even odd even odd
Reordered: 1 → 3 → 5 → 2 → 4 → null
↑___↑___↑ ↑___↑
odd nodes even nodes
Example 2:
Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]
Visual:
Original: 2 → 1 → 3 → 5 → 6 → 4 → 7 → null
↑ ↑ ↑ ↑ ↑ ↑ ↑
odd even odd even odd even odd
Reordered: 2 → 3 → 6 → 7 → 1 → 5 → 4 → null
↑___↑___↑___↑ ↑___↑___↑
odd positions even positions
Constraints:
- The number of nodes in the linked list is in the range [0, 10^4].
- -10^6 <= Node.val <= 10^6
🌟 ELI5: The Simple Idea!
Think of separating kids by position in line:
Original line: [1, 2, 3, 4, 5]
↑ ↑ ↑ ↑ ↑
pos1 2 3 4 5
Task: Odd positions first, then even positions
Odd positions (1, 3, 5): [1, 3, 5]
Even positions (2, 4): [2, 4]
New line: [1, 3, 5] + [2, 4] = [1, 3, 5, 2, 4] ✓
Key Insight: Build two separate chains, then connect!
Original: 1 → 2 → 3 → 4 → 5
Build odd chain: 1 → 3 → 5
Build even chain: 2 → 4
Connect: 1 → 3 → 5 → 2 → 4 ✓
🎨 Visual Understanding
The Separation Process
Original: 1 → 2 → 3 → 4 → 5 → null
Step by step:
Initial:
odd = 1, even = 2, evenHead = 2
1 → 2 → 3 → 4 → 5 → null
↑ ↑
odd even
Iteration 1:
odd.next = even.next (3)
1 → 3 → 4 → 5 → null
↑
odd moves to 3
even.next = odd.next (4)
2 → 4 → null
↑
even moves to 4
State:
Odd chain: 1 → 3 → 5
Even chain: 2 → 4
Iteration 2:
odd.next = even.next (5)
1 → 3 → 5 → null
↑
odd moves to 5
even.next = odd.next (null)
2 → 4 → null
even is null, exit loop
Final: Connect odd chain to even chain
odd.next = evenHead
1 → 3 → 5 → 2 → 4 → null ✓
🎯 Approach: Two Pointers (Odd & Even) ⭐
The Optimal Solution
Algorithm:
1. Create two pointers: odd and even
2. Save even head (to connect later)
3. While even and even.next exist:
- odd.next = even.next (skip even)
- odd = odd.next (move odd)
- even.next = odd.next (skip odd)
- even = even.next (move even)
4. Connect: odd.next = evenHead
Implementation
/**
* Two-pointer approach: separate odd and even chains
* Time: O(n), Space: O(1)
*/
public ListNode oddEvenList(ListNode head) {
// Edge cases
if (head == null || head.next == null) {
return head;
}
// Initialize pointers
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even; // Save even head for later connection
// Separate odd and even nodes
while (even != null && even.next != null) {
// Connect odd nodes
odd.next = even.next;
odd = odd.next;
// Connect even nodes
even.next = odd.next;
even = even.next;
}
// Connect odd chain to even chain
odd.next = evenHead;
return head;
}
⏰ Time: O(n) - Single pass through the list
💾 Space: O(1) - Only three pointers
🔍 Super Detailed Dry Run
Example: head = [1, 2, 3, 4, 5]
Goal: Reorder to [1, 3, 5, 2, 4]
Initial state:
head → 1 → 2 → 3 → 4 → 5 → null
odd = head = 1
even = head.next = 2
evenHead = even = 2
State:
1 → 2 → 3 → 4 → 5 → null
↑ ↑
odd even
evenHead = 2
═══════════════════════════════════════════════════════════════
Iteration 1
═══════════════════════════════════════════════════════════════
Condition: even != null (2) && even.next != null (3) ✓
Step 1: Connect odd nodes
odd.next = even.next
1.next = 3
Before:
1 → 2 → 3 → 4 → 5
After:
1 ──────→ 3 → 4 → 5
2 → 3
Move odd:
odd = odd.next = 3
Step 2: Connect even nodes
even.next = odd.next
2.next = 4
Before:
2 → 3 → 4
After:
2 ──────→ 4 → 5
3 → 4
Move even:
even = even.next = 4
State after iteration 1:
Odd chain: 1 → 3 → 4 → 5
↑
odd
Even chain: 2 → 4 → 5
↑
even
evenHead still points to 2
═══════════════════════════════════════════════════════════════
Iteration 2
═══════════════════════════════════════════════════════════════
Condition: even != null (4) && even.next != null (5) ✓
Step 1: Connect odd nodes
odd.next = even.next
3.next = 5
Before:
1 → 3 → 4 → 5
After:
1 → 3 ──────→ 5 → null
4 → 5
Move odd:
odd = odd.next = 5
Step 2: Connect even nodes
even.next = odd.next
4.next = null (5.next is null)
Before:
2 → 4 → 5
After:
2 → 4 → null
Move even:
even = even.next = null
State after iteration 2:
Odd chain: 1 → 3 → 5 → null
↑
odd
Even chain: 2 → 4 → null
↑
even
evenHead still points to 2
═══════════════════════════════════════════════════════════════
Loop Exit & Connect
═══════════════════════════════════════════════════════════════
Condition: even != null (null) ✗
Exit loop!
Connect odd and even chains:
odd.next = evenHead
5.next = 2
1 → 3 → 5 → 2 → 4 → null
═══════════════════════════════════════════════════════════════
Return Result
═══════════════════════════════════════════════════════════════
Return: head (node 1)
Final list: 1 → 3 → 5 → 2 → 4 → null ✓
Result: [1, 3, 5, 2, 4]
Example 2: head = [1, 2, 3, 4]
Even length example
Initial:
odd = 1, even = 2, evenHead = 2
1 → 2 → 3 → 4 → null
↑ ↑
odd even
Iteration 1:
odd.next = 3
odd = 3
even.next = 4
even = 4
Odd: 1 → 3 → 4
Even: 2 → 4
Iteration 2:
Condition: even (4) && even.next (null) ✗
Exit!
Connect:
odd.next = evenHead
3.next = 2
1 → 3 → 2 → 4 → null ✓
Works for even length too!
🎯 Why This Algorithm Works
The Two-Chain Concept
At each step, we're building two independent chains:
Original: 1 → 2 → 3 → 4 → 5
Odd chain construction:
Start: 1
Add: 1 → 3 (skip 2)
Add: 1 → 3 → 5 (skip 4)
Even chain construction:
Start: 2
Add: 2 → 4 (skip 3)
End: 2 → 4 → null (skip 5)
Then connect: odd.next = evenHead
Why Save evenHead?
Without saving:
even pointer moves through the chain
At the end, even = null (or last even node)
We lose reference to first even node!
Can't connect! ❌
With evenHead:
evenHead always points to first even node (2)
even pointer can move freely
At the end: odd.next = evenHead ✓
Loop Condition Explained
while (even != null && even.next != null)
Why both conditions?
even != null:
If list has odd length, even becomes null
[1, 2, 3] → even moves 2 → null
even.next != null:
If list has even length, even.next becomes null
[1, 2, 3, 4] → even at 4, even.next = null
Both ensure we don't access null.next!
⚠️ Common Mistakes
Mistake 1: Not saving evenHead
// ❌ WRONG - Lost reference to even chain!
ListNode odd = head;
ListNode even = head.next;
// Forgot: ListNode evenHead = even;
while (...) {
// even pointer moves
}
odd.next = even; // even might be null or wrong node!
// ✓ CORRECT - Save before moving
ListNode evenHead = even;
// ...
odd.next = evenHead;
Mistake 2: Wrong loop condition
// ❌ WRONG - Can cause null pointer exception
while (even != null) {
odd.next = even.next; // What if even.next is null?
}
// ✓ CORRECT - Check both
while (even != null && even.next != null) {
// Safe to access even.next
}
Mistake 3: Moving pointers before updating next
// ❌ WRONG - Lost reference!
odd = odd.next; // Moved too early!
odd.next = even.next; // Wrong odd!
// ✓ CORRECT - Update next first, then move
odd.next = even.next;
odd = odd.next;
Mistake 4: Trying to create new nodes
// ❌ WRONG - Wastes space, not in-place
ListNode oddList = new ListNode(0);
ListNode evenList = new ListNode(0);
// ... build new lists ...
// ✓ CORRECT - Reuse existing nodes
// Just rearrange pointers!
Mistake 5: Forgetting to connect chains
// ❌ WRONG - Two separate chains!
while (...) {
// Build odd and even chains
}
// Forgot: odd.next = evenHead
return head; // Only returns odd chain!
// ✓ CORRECT - Connect them
odd.next = evenHead;
return head;
🎯 Pattern Recognition
Problem Type: Reorder by Position (Odd/Even)
Core Pattern: Two-Pointer Separation
When to Apply:
✓ Group by position (odd/even)
✓ Reorder while maintaining relative order
✓ Separate into two groups
✓ In-place rearrangement
Recognition Keywords:
- "odd indices"
- "even indices"
- "group by position"
- "maintain relative order"
- "O(1) space"
Similar Problems:
- Partition List (LC 86) - Separate by value
- Reorder List (LC 143) - Different pattern
- Split Linked List in Parts (LC 725) - Multiple groups
Key Components:
┌────────────────────────────────────────────┐
│ Two Pointers: odd and even │
│ Save Head: evenHead for connection │
│ Build Chains: Skip alternating nodes │
│ Connect: odd.next = evenHead │
│ Time: O(n), Space: O(1) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "I need to separate odd and even positioned nodes"
Step 2: "I'll use two pointers to build separate chains"
Step 3: "Then connect odd chain to even chain"
Key Points to Mention:
- Two pointers: one for odd, one for even
- Save even head before moving pointers
- Skip alternating nodes to build chains
- Maintain relative order automatically
- Connect chains at the end
- Time: O(n), Space: O(1) in-place
Walk Through Example:
"For [1,2,3,4,5]:
Start: odd=1, even=2, save evenHead=2
Iteration 1:
odd.next = 3 (skip 2)
even.next = 4 (skip 3)
Iteration 2:
odd.next = 5 (skip 4)
even.next = null
Connect: 5.next = evenHead (2)
Result: [1,3,5,2,4]"
Why Two Pointers:
"Each pointer builds its own chain
by skipping the other type of nodes.
Odd skips even, even skips odd.
This maintains relative order automatically."
Edge Cases to Mention:
✓ Empty list → return null
✓ Single node → return as is
✓ Two nodes → swap them
✓ Odd length → last node is odd
✓ Even length → both chains equal
📝 Quick Revision Notes
🎯 Core Concept:
Odd Even Linked List: Use two pointers to build separate chains. Save evenHead before moving! Odd skips even (odd.next = even.next), even skips odd (even.next = odd.next). Loop while even && even.next exist. Finally connect: odd.next = evenHead. O(1) space!
⚡ Quick Implementation:
import java.util.Arrays;
import java.util.List;
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public static ListNode create(List<Integer> list) {
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
for(int num : list) {
curr.next = new ListNode(num);
curr = curr.next;
}
return dummy.next;
}
public static void print(ListNode head) {
ListNode curr = head;
while (curr != null) {
System.out.print(curr.val + " -> ");
curr = curr.next;
}
System.out.println();
}
public ListNode oddEvenList(ListNode head) {
// same for 0/1/2 elements.
if(head == null || head.next == null || head.next.next == null) {
return head;
}
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
// Both works.
// while (odd != null && odd.next != null && even != null && even.next != null) {
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
// Linking odd and even lists.
odd.next = evenHead;
return head;
}
public static void main(String[] args) {
Solution t = new Solution();
ListNode list1 = create(Arrays.asList(1, 2, 3, 4, 5));
print(t.oddEvenList(list1));
print(t.oddEvenList(create(Arrays.asList(-1, 5, 3, 4, 0))));
print(t.oddEvenList(create(Arrays.asList(0)))); // 1 element
print(t.oddEvenList(create(Arrays.asList(0, 1)))); // 2 elements
print(t.oddEvenList(create(Arrays.asList(2, 1)))); // 2 elements
print(t.oddEvenList(create(Arrays.asList(2, 1, 5)))); // odd count
print(t.oddEvenList(create(Arrays.asList(2, 1, -4, 0)))); // even count
print(t.oddEvenList(create(Arrays.asList(1, 2, 3, 4, 5)))); // strictly increasing
print(t.oddEvenList(create(Arrays.asList(5, 4, 3, 2)))); // strictly decreasing
}
}
🔑 Key Insights:
- Pattern: Two-Pointer Separation
- Save evenHead: Before moving even pointer
- Skip pattern: odd → even.next, even → odd.next
- Loop: while even && even.next
- Connect: odd.next = evenHead (critical!)
- Time: O(n), Space: O(1) ✓
🎪 Memory Aid:
"Two chains, skip between, save and connect!"
"Odd skips even, even skips odd!" ✨
⚠️ Critical Steps:
1. Save evenHead FIRST
2. Loop: even && even.next
3. Update next BEFORE moving
4. Connect at end: odd.next = evenHead
Without evenHead → LOST!
Wrong loop → NULL POINTER!
🧪 Edge Cases
Case 1: Empty list
Input: head = null
Output: null
Handled: Early return
Case 2: Single node
Input: head = [1]
Output: [1]
Handled: Early return
Case 3: Two nodes
Input: head = [1,2]
Output: [1,2]
Loop doesn't run, already correct
Case 4: Odd length
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
Last node is odd, works correctly
Case 5: Even length
Input: head = [1,2,3,4]
Output: [1,3,2,4]
Both chains equal length, works correctly
All handled perfectly! ✓
Related Problems
- Partition List (LC 86) - Separate by value, similar two-pointer
- Reorder List (LC 143) - Different reordering pattern
- Split Linked List in Parts (LC 725) - Multiple groups
Happy practicing! 🎯
Note: This problem teaches the two-pointer separation pattern for linked lists! The key insight is building two independent chains simultaneously by having each pointer skip the other type's nodes. This pattern appears in many partition/grouping problems. Master the "save head, build chains, connect" technique! 💪✨