Odd Even Linked List | Multiple Approaches

1. Problem Statement and Objective

The Odd Even Linked List problem requires us to take a singly linked list and group all the nodes at odd indices together, followed immediately by all the nodes at even indices. We must preserve the relative order of nodes within both the odd group and the even group.

Key Rules

• 1-Based Indexing: The problem uses 1-based indexing for node positions (e.g., $1\text{st}, 2\text{nd}, 3\text{rd}, \dots$).
• In-Place Reordering (Optimal): While a brute-force approach can use extra memory, the interviewer's ultimate goal is an $O(1)$ space solution using pointer manipulations.
• Return Value: Return the head of the modified linked list.

Visualizing the Transformation

2. Approach 1: The Brute Force Method (Data Replacement)

Core Intuition

Before diving into complex pointer adjustments, a naive approach is to decouple the problem: extract all data values from odd-index nodes, extract all data values from even-index nodes, store them in an external data structure (like an array or list), and then write those values back into the linked list sequentially.

Step-by-Step Execution

1. Handle Base Cases: If the linked list is empty (head == null) or has only a single node (head.next == null), return the head immediately without any processing.
2. Collect Odd-Index Data:
   • Initialize a temporary pointer at head.
   • Traverse the list by jumping two steps at a time (temp = temp.next.next) to collect data from indices $1, 3, 5, \dots$ into an array.
3. Collect Even-Index Data:
   • Initialize a temporary pointer at head.next.
   • Traverse the list jumping two steps at a time to collect data from indices $2, 4, 6, \dots$ into the same array (or a separate array).
4. Rewrite Data:
   • Reset the temporary pointer to head and an index tracker i = 0 for the array.
   • Overwrite the linked list nodes' values sequentially with the values stored in the array.

Brute Force Pseudo-Code

// Step 1: Edge cases
if (head == null || head.next == null) return head;

List<Integer> list = new ArrayList<>();
TempNode temp = head;

// Step 2: Collect odd-index data
while (temp != null && temp.next != null) {
    list.add(temp.data);
    temp = temp.next.next;
}
if (temp != null) {
    list.add(temp.data); // Catch last element for odd-length lists
}

// Step 3: Collect even-index data
temp = head.next;
while (temp != null && temp.next != null) {
    list.add(temp.data);
    temp = temp.next.next;
}
if (temp != null) {
    list.add(temp.data); // Catch last element for even-length lists
}

// Step 4: Write back to the linked list
temp = head;
int i = 0;
while (temp != null) {
    temp.data = list.get(i++);
    temp = temp.next;
}

return head;

3. Complexity Analysis of Brute Force

4. The Optimization Pivot: Why External Space Fails the Interview

An interviewer will typically reject the brute-force solution with:

"I'm not happy with the external space that you're using. Can you please optimize it to $O(1)$ auxiliary space?"

This constraint mandates that we rearrange the links (pointers) of the nodes themselves rather than swapping data or allocating new data structures. We must perform all wiring directly inside the existing memory layout.

5. Approach 2: Optimal Pointer Manipulation ($O(1)$ Space)

Core Mental Model

Think of the linked list as a zip fastener. We maintain two distinct traversal chains:

1. Odd Chain: Starts at head (index 1).
2. Even Chain: Starts at head.next (index 2). We also memorize the start of the even chain (evenHead) so we can attach it to the end of the odd chain later.

Step-by-Step Pointer Evolution

During each iteration inside a single loop, we perform two link rewiring operations simultaneously:

1. Re-route Odd Pointer: Connect current odd.next to odd.next.next, then advance odd.
2. Re-route Even Pointer: Connect current even.next to even.next.next, then advance even.

Iteration 1:
- odd.next points to odd.next.next ([1] now points to [3])
- even.next points to even.next.next ([2] now points to [4])
- Advance odd to [3], advance even to [4]

Iteration 2:
- odd.next points to odd.next.next ([3] now points to [5])
- even.next points to even.next.next ([4] now points to [6])
- Advance odd to [5], advance even to [6]

6. Real-World Practical Pitfalls & Edge Cases

Edge Case 1: Null or Single Node Lists

If the list has 0 or 1 node, no grouping is required.

if (head == null || head.next == null) {
    return head;
}

Edge Case 2: Connecting Odd Tail to Even Head

Once the traversal loop terminates, our odd pointer rests at the last node of the odd chain (e.g., node [5]), while even rests at the end of the even chain. However, node [5]'s next pointer is currently pointing to [6].

We must fix this by bridging the tail of the odd chain to the saved evenHead:

odd.next = evenHead;

7. Complete Optimized Pseudo-Code

Here is the complete implementation for the optimal $O(1)$ space approach:

public ListNode oddEvenList(ListNode head) {
    // 1. Handle edge cases
    if (head == null || head.next == null) {
        return head;
    }

    // 2. Initialize pointers and memorize even head
    ListNode odd = head;
    ListNode even = head.next;
    ListNode evenHead = even; // Save the start of the even chain

    // 3. Traverse and rewire links simultaneously
    while (even != null && even.next != null) {
        odd.next = odd.next.next;     // Connect odd to next odd
        even.next = even.next.next;   // Connect even to next even
        
        odd = odd.next;               // Advance odd pointer
        even = even.next;             // Advance even pointer
    }

    // 4. Connect the tail of odd chain to the head of even chain
    odd.next = evenHead;

    // 5. Return the modified list head
    return head;
}

8. Dry Run Walkthrough

Let's trace the optimal algorithm with a concrete example: 1 -> 2 -> 3 -> 4 -> 5 -> NULL.

Initial State

• head = 1
• odd = 1
• even = 2
• evenHead = 2

Loop Iteration 1

• Condition Check: even (2) != null and even.next (3) != null $\rightarrow$ True.
• Odd Link Change: odd.next = odd.next.next $\rightarrow$ Node 1's next becomes 3. (1 -> 3 -> 2 -> 4 -> 5)
• Even Link Change: even.next = even.next.next $\rightarrow$ Node 2's next becomes 4. (1 -> 3 -> 2 -> 4 -> 5)
• Advance Pointers:
  • odd moves to odd.next (Node 3).
  • even moves to even.next (Node 4).

Loop Iteration 2

• Condition Check: even (4) != null and even.next (5) != null $\rightarrow$ True.
• Odd Link Change: odd.next = odd.next.next $\rightarrow$ Node 3's next becomes 5. (1 -> 3 -> 5 -> 4 -> NULL)
• Even Link Change: even.next = even.next.next $\rightarrow$ Node 4's next becomes null. (1 -> 3 -> 5 -> 4 -> NULL)
• Advance Pointers:
  • odd moves to odd.next (Node 5).
  • even moves to even.next (null).

Loop Termination

• even is now null. Loop terminates.
• Post-Loop Stitching: odd.next = evenHead $\rightarrow$ Node 5 points to 2.
• Final Structure: 1 -> 3 -> 5 -> 2 -> 4 -> NULL.
• Return: head (1).

9. Summary and Key Takeaways

• Problem Definition: Group odd-indexed nodes together followed by even-indexed nodes while maintaining relative order.
• Brute Force Flaw: Utilizing external arrays or lists takes $O(N)$ extra space, which fails optimal interview requirements.
• Optimal Strategy: Use three pointer references (odd, even, and evenHead) to rewire links in-place.
• Loop Condition: The traversal loop relies strictly on the even pointer (while (even != null && even.next != null)) because the even pointer always leads the odd pointer.
• Memorization is Crucial: Saving evenHead before traversal allows us to bridge the odd tail to the even head at the end.
• Time Complexity: $O(N)$ as the pointer traverses half the list elements ($\frac{N}{2}$ iterations).
• Space Complexity: $O(1)$ auxiliary space since no external data structures are allocated.