Odd Even Linked List — Two-Chain In-Place Grouping Explained

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 appeared in the input. You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Constraints:

• The number of nodes in the linked list is in the range [0, 10^4]
• -10^6 <= Node.val <= 10^6

Example 1:

Input:  head = [1, 2, 3, 4, 5]
Output: [1, 3, 5, 2, 4]
Explanation: Odd-indexed nodes (1,3,5) come first, then even-indexed (2,4).

Example 2:

Input:  head = [2, 1, 3, 5, 6, 4, 7]
Output: [2, 3, 6, 7, 1, 5, 4]

Example 3:

Input:  head = [1, 2]
Output: [1, 2]

Why This Problem Matters#

Odd Even Linked List (LeetCode 328) is asked at Facebook, Amazon, and LinkedIn because it tests a specific skill: maintaining two separate pointer chains simultaneously while traversing the list once. Unlike most linked list problems that work with a single cursor, this problem requires you to interleave updates across two chains without losing track of either.

The key constraint — O(1) extra space — rules out any solution that creates a separate list or collects values. You must rearrange in place by rewiring pointers, which requires precise choreography of the odd, even, and evenHead pointers.

This pattern is a generalization of "partition a linked list by a condition." Here the condition is index parity (odd vs even position). In Partition List (LC 86), the condition is value comparison against a pivot. Once you master the two-chain approach, both problems feel similar.

In real-world systems, rearranging elements by parity or alternation appears in certain scheduling algorithms (round-robin with two priority classes), memory management (interleaved data blocks), and data serialization formats that alternate metadata and payload blocks.

The Core Insight#

Maintain two chains simultaneously:

• odd: the tail of the odd-index chain, starts at node 1 (head)
• even: the tail of the even-index chain, starts at node 2 (head.next)
• evenHead: the head of the even chain (saved so we can connect it at the end)

At each iteration:

1. Wire odd.next = even.next (odd chain skips over the even node to grab the next odd node)
2. Advance odd = odd.next
3. Wire even.next = odd.next (even chain grabs the next even node)
4. Advance even = even.next

When the loop ends, connect: odd.next = evenHead.

The loop continues while even and even.next — if even is None (even-length list exhausted) or even.next is None (no next odd node), we stop.

Visual Dry Run#

Input: 1 -> 2 -> 3 -> 4 -> 5

Initial state: odd = 1, even = 2, evenHead = 2

Loop check: even is None → stop.

Connect: odd.next = evenHead → 5.next = 2

Output: 1 -> 3 -> 5 -> 2 -> 4

Solution (Optimal)#

Python#

def oddEvenList(head):
    if not head:
        return head
    
    odd = head          # tail of odd-index chain
    even = head.next    # tail of even-index chain
    evenHead = even     # save even chain head to connect at the end
 
    while even and even.next:
        odd.next = even.next    # odd chain: skip even, grab next odd
        odd = odd.next          # advance odd tail
        even.next = odd.next    # even chain: grab next even
        even = even.next        # advance even tail
 
    odd.next = evenHead  # connect odd chain tail to even chain head
    return head          # head (node 1) is still the start of the odd chain

Time complexity: O(n) — single pass.

Space complexity: O(1) — only three pointer variables.

JavaScript#

var oddEvenList = function(head) {
    if (head === null) return head;
    
    let odd = head;
    let even = head.next;
    const 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;
};

Complexity:

Common Mistakes#

1. Not saving evenHead. The even chain's head is head.next. After the loop, you need odd.next = evenHead to reconnect. If you lose this reference (by not saving it before the loop starts), you can't reconnect.

2. Using the wrong loop termination condition. The condition must be while even and even.next. If the list has an even number of nodes, even becomes None (both chains exhausted simultaneously). If odd, even.next becomes None (even chain has no next odd to grab). Checking only even doesn't protect even.next access.

3. Confusing index-based vs value-based grouping. This problem groups by index parity (position 1, 3, 5 vs 2, 4, 6), not value parity. A list [2, 1, 3] produces [2, 3, 1] — node at index 1 (value 2) and index 3 (value 3) are "odd," node at index 2 (value 1) is "even." This trips up many candidates.

4. Forgetting the empty or single-node case. If head = None, head.next crashes. The if not head: return head guard prevents this. If head.next = None, even = None, the loop doesn't execute, odd.next = None (evenHead). Correct.

5. Advancing odd before even in the wrong order. The order odd.next = even.next; odd = odd.next must come before even.next = odd.next; even = even.next. After advancing odd, odd.next points to the correct next-even node. If you advance even first, you lose the reference to the next-odd node.

Interview Tips#

1. Name the three pointers immediately: "I'll use three pointers: odd (odd chain tail), even (even chain tail), and evenHead (even chain head, saved for reconnection)."

2. Emphasize the order: "I update odd first, advance odd, then update even from the new odd.next. Order matters — I'll walk through it."

3. Test even-length and odd-length lists: [1, 2, 3, 4] produces [1, 3, 2, 4] (even nodes 2 and 4 come after). [1, 2, 3, 4, 5] produces [1, 3, 5, 2, 4].

4. State the O(1) space property: The problem constraint demands it — confirm you're meeting it with only pointer variables.

5. Bridge to Partition List: "This is similar to LC 86 Partition List — both maintain two chains and connect them. There the split condition is value-based, here it's index parity."

Follow-up Questions#

Q: How does this differ from Partition List (LC 86)? Partition List groups by value comparison against a pivot, preserving relative order in each group. Odd Even List groups by index parity, also preserving relative order. Both use the two-chain technique, but Partition List uses a dummy head for each chain.

Q: What if you want value-parity grouping (even values first, then odd values)? Replace the index-based alternation with a value check: if head.val % 2 == 0: attach to even chain, else: attach to odd chain. You'd need a different iteration approach since you're not alternating by position.

Q: What if you want even-indexed nodes first? Just swap odd and even initialization: even = head (start of even chain), odd = head.next. Connect even.next = oddHead at the end.

Q: What's the time complexity? O(n) — you visit each node exactly once, either when advancing odd or when advancing even. Each node's .next is updated at most twice.

Q: What if the list is doubly linked? The algorithm works identically — you'd additionally need to update prev pointers in the doubly linked structure. The same two-chain logic applies.

Key Takeaways#

• Use three pointers: odd (odd chain tail), even (even chain tail), evenHead (even chain head saved before the loop).
• Update odd chain first, advance odd, then update even chain from the new odd.next, advance even.
• The loop condition is while even and even.next — protects both .next accesses inside the loop.
• After the loop: odd.next = evenHead reconnects the two chains.
• O(1) space, O(n) time — exactly one pass, three pointer variables.
• This is index-parity grouping — not value-parity. Position 1, 3, 5... are "odd," not values 1, 3, 5...