Algorithm

Odd Even Linked List

Linked List Pattern

Odd Even Linked List

Reorder a singly linked list such that all nodes at odd indices (1st, 3rd, 5th...) come first, followed by all nodes at even indices (2nd, 4th, 6th...). The relative order within each group must be preserved.

CONSTRAINTS
  • The number of nodes is in the range [0, 10,000]
  • -1,000,000 <= Node.val <= 1,000,000
  • Must solve in **O(1) extra space** and **O(N) time**.
EXAMPLE 1
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
The 1st, 3rd, and 5th nodes (values 1, 3, 5) are grouped at the front. The 2nd and 4th nodes (values 2, 4) follow them.
EXAMPLE 2
Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]
The nodes at odd positions (2, 3, 6, 7) are pulled forward, while even-position nodes (1, 5, 4) form the tail.
EXAMPLE 3
Input: head = [1]
Output: [1]
A single node list is already partitioned by definition. No traversal is necessary.
Is this based on the node's value or its position?
Position. The 1st node, 2nd node, 3rd node... regardless of whether the internal value is 10, 5, or 100.
Do relative orders within the odd and even groups need to be preserved?
Yes. If the original order was (1, 3, 5), the output must keep them as (1, 3, 5) without swapping.
What should return for an empty list?
An empty list should return null immediately.

Rearranging a linked list by position means grouping all nodes at odd indices (1st, 3rd, 5th...) at the beginning, followed by all nodes at even indices (2nd, 4th, 6th...). This must happen in-place to satisfy memory constraints.

The most intuitive way is to traverse and collect nodes into two separate arrays (odds and evens) and then link them. However, this uses O(N) extra space. To optimize to O(1) space, we must manipulate pointers directly.

We build two concurrent chains using three roles: an odd writer, an even writer, and an evenHead safety anchor that stays at the start of the even chain so we can bridge the two halves later.

As we move through the list, we perform a "leapfrog" surgery. The odd pointer skips over the current even node to link to the next available odd node. Then, the even pointer skips over the new odd node to link to the next even node.

python
odd = head
even = head.next
even_head = even

# even and even.next must exist to leapfrog
while even and even.next:
    # 1. Odd jumps over even
    odd.next = even.next
    odd = odd.next
    
    # 2. Even jumps over the new odd
    even.next = odd.next
    even = even.next

# 3. The Bridge: Link the end of odd to the start of even
odd.next = even_head

The loop handles both even and odd length lists automatically. In even-length lists, even.next becomes null; in odd-length lists, even itself becomes null. In both cases, the odd pointer finishes at the true end of the odd chain.

Worked Example:[1, 2, 3, 4, 5]
1
odd
→
2
evenevenHead
→
3
→
4
→
5
→
NULL
We set 'odd' at the head (1), 'even' at the second node (2), and lock 'evenHead' at 2 as our bridge anchor.

Step 2: First Leapfrog

1
→
3
odd
→
NULL
Odd Chain: Node 1 links past 2 directly to 3. We advance 'odd' to 3.
2
evenHead
→
4
even
→
NULL
Even Chain: Node 2 links past 3 directly to 4. We advance 'even' to 4.

Step 3: Second Leapfrog

1
→
3
→
5
odd
→
NULL
Odd Chain: Node 3 links past 4 directly to 5. We advance 'odd' to 5.
2
evenHead
→
4
→
NULL
Even Chain: Node 4 links past 5 to null. 'even' becomes null, terminating the loop.

Step 4: The Bridge Stitch

1
→
3
→
5
→
2
→
4
→
NULL
Finally, we stitch the odd tail (5) directly to 'evenHead' (2) to connect the two chains, yielding [1, 3, 5, 2, 4].
Interactive Strategy Visualization
INDEX REORDERING ENGINE

Relative Parity Transformation

1Odd2EvenEVEN HEAD345

Operation Step

Phase 1: Dual Track Setup

We launch two independent cursors. Odd claims the first node, while Even takes the second. We cache the Even Head as an anchor for the final re-join.

Memory Threading

We are essentially threading two disjoint lists through the same memory space, then tying them together at the midpoint.

Strategy: Relative Index Leapfrogging

By advancing cursors two nodes at a time, we reorganize the entire topology in a single O(N) pass using just O(1) extra space.

O(N) Time · O(N) Space Two Buffers
→
O(N) Time · O(1) Space In-Place Braid