Odd Even Linked List: Two-Group Partition

May 18, 20265 min read

leetcodeproblemmediumlinked-lists

Odd Even Linked List is LeetCode problem 328. You are given the head of a singly linked list. Group all nodes at odd indices together, then all nodes at even indices, and return the reordered list. The first node is considered odd, the second is even, and so on. The relative order within each group must be preserved.

Example: [1, 2, 3, 4, 5] becomes [1, 3, 5, 2, 4].

Odd-indexed nodes (accent) are gathered first, even-indexed nodes (warning) follow. The odd tail splices into the even head to form the result.

The nodes do not move. Only the next pointers get rewired. You are not creating any new nodes or copying any values.

The key insight

The trick is to maintain two sub-lists simultaneously as you scan the original list: one for odd-indexed nodes and one for even-indexed nodes. You weave the next pointers as you walk forward, alternating between the two chains.

The only thing you need to save upfront is a reference to the head of the even group, evenHead. That reference stays fixed for the whole algorithm. Once the loop finishes, you splice the even group onto the tail of the odd group with a single assignment: odd.next = evenHead.

This works because:

You rewire next pointers in-place. No new nodes are allocated.
Both chains are built by skipping every other node, so relative order is automatically preserved.
The even group starts at head.next. Saving that reference before the loop lets you perform the final splice even though the even pointer may have advanced far away by then.

Practice this pattern

The algorithm

If the list is empty or has only one node, return head immediately.
Set odd = head, even = head.next, evenHead = even.
While even and even.next both exist:
- odd.next = even.next (skip the even node, link odd to the next odd node)
- odd = odd.next (advance the odd pointer)
- even.next = odd.next (skip the odd node, link even to the next even node)
- even = even.next (advance the even pointer)
odd.next = evenHead (splice the even group onto the odd tail)
Return head.

The loop condition even and even.next guards against two failure modes. even being None means you have exhausted even nodes. even.next being None means there are no more odd nodes to connect to, so the loop is done.

The code

def oddEvenList(head):
    if not head:
        return head
    odd = head
    even = 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 head

A few things worth noting:

odd.next = even.next skips over the current even node and hooks the odd pointer to the next odd node. At this point, even.next is a node at an odd index.
odd = odd.next advances the odd pointer to that newly connected node.
even.next = odd.next now looks ahead from the new odd node to find the next even node, and wires the even chain to it.
even = even.next advances the even pointer.
odd.next = even_head at the end does the splice. If the input list is empty, even_head is None, and odd.next was already None, so this is safe.

Initialize: odd = node 1, even = node 2, evenHead = node 2

Set odd to head (node 1) and even to head.next (node 2). Save a permanent reference to evenHead so you can splice after the loop.

Iteration 1: wire 1 to 3, wire 2 to 4. Advance both pointers.

odd.next = even.next (node 3), then odd advances to node 3. Even.next = odd.next (node 4), then even advances to node 4.

Iteration 2: wire 3 to 5, advance odd. even.next = None, loop ends.

odd.next = even.next (node 5), odd advances to node 5. even.next = odd.next which is None (node 5 was the last), so even becomes None and the while condition fails.

Splice: odd.next = evenHead (node 2). The two groups are linked.

odd currently points to node 5 (the tail of the odd group). Setting odd.next = evenHead attaches the full even group onto the end of the odd group.

Result: return head. The list is now [1, 3, 5, 2, 4].

The head pointer was never moved, so returning it gives the reordered list. All odd-indexed nodes precede all even-indexed nodes, and relative order within each group is preserved.

Complexity analysis

Metric	Value	Reasoning
Time	O(n)	You visit every node exactly once in a single forward pass.
Space	O(1)	Only a fixed number of pointer variables are used. No new nodes are created.

This is optimal. Every node must be examined at least once to determine whether it belongs to the odd or even group.

Drill this solution with spaced repetition

Building blocks

This problem is built from three reusable ideas that appear throughout linked list problems.

Two-pointer technique

You maintain two pointers (odd and even) that advance through the list in lockstep, each responsible for one chain. Neither pointer ever goes backward. Neither skips more than two nodes in a single step. Together they partition every node in a single pass.

This same coordination between two simultaneous pointers shows up in Linked List Cycle (slow and fast), in merge sort for linked lists, and in the partition problems.

In-place linked list rewiring

You never allocate new nodes. Instead, you change where existing next pointers point. This is the fundamental building block of in-place linked list manipulation. The discipline required here, saving a reference before you overwrite a pointer, is the same discipline needed in Reverse Linked List.

The "save the head" pattern

You save evenHead = even before the loop starts. Without it, you cannot do the final splice because the even pointer has been advanced far into the list. Saving the head of a sub-list before you start modifying pointers is a recurring pattern. It appears in merge operations, in partition problems, and any time you build a sub-list and need to reference its beginning later.

Edge cases

Empty list. head is None, so the guard at the top returns immediately. Safe.
Single node. even = head.next is None. The loop condition fails. odd.next = evenHead sets odd.next = None, which it already was. Returns the single node correctly.
Two nodes. odd = node 1, even = node 2, evenHead = node 2. Loop condition: even is truthy, but even.next is None, so the loop does not run. odd.next = evenHead points node 1 to node 2, which it already did. Returns [1, 2] unchanged. Correct.
Already odd-even-sorted list. The algorithm still runs and produces the correct output. It rewires each pointer to where it already points, which is a no-op in effect. No special casing needed.
Even-length list (e.g., [1, 2, 3, 4]). The odd group is [1, 3] and the even group is [2, 4]. The loop terminates when even.next is None (after even has advanced to node 4). The splice produces [1, 3, 2, 4]. Correct.

From understanding to recall

This solution looks simple on paper. Two pointers, one loop, one splice. But under interview pressure, the details blur fast. Which pointer advances first inside the loop: odd or even? What exactly does the loop condition check? Why save evenHead at all?

The only way to make these details automatic is repetition. Type the solution from scratch, several times, with increasing gaps between sessions. The first rep you check your notes. By the third or fourth rep, the order of operations is locked in and you stop second-guessing.

Try CodeBricks free

Partition List - same partition-then-splice pattern on a different predicate
Reverse Linked List - fundamental in-place linked list rewiring
Linked List Cycle - another two-pointer linked list technique