Odd Even Linked List

Odd Even Linked List

What is this problem about?

The Odd Even Linked List problem asks you to rearrange a linked list so that all odd-indexed nodes come before all even-indexed nodes (1-indexed), maintaining relative order within each group. This must be done in O(1) space and O(n) time. This coding problem is a classic linked list pointer manipulation exercise.

Why is this asked in interviews?

Apple, Microsoft, Meta, Amazon, Google, Bloomberg, and many others ask this because it tests in-place linked list rearrangement without extra space. Maintaining two sub-lists (odd and even) and connecting them is a fundamental linked list skill. The linked list interview pattern is the core.

Algorithmic pattern used

Two-pointer list splitting. Maintain odd (pointer to last odd-indexed node) and even (pointer to last even-indexed node), plus evenHead (first even-indexed node). While even != null and even.next != null: connect odd to even.next (skip even node), advance odd; connect even to odd.next (skip next odd node), advance even. Finally, connect odd.next = evenHead.

Example explanation

List: 1→2→3→4→5.

• odd=1, even=2, evenHead=2.
• Step 1: odd.next=3, odd=3. even.next=4, even=4.
• Step 2: odd.next=5, odd=5. even.next=null, even=null.
• Connect: 5.next=evenHead=2. Result: 1→3→5→2→4.

Common mistakes candidates make

• Losing the evenHead pointer before the final connection.
• Not terminating the loop correctly (check both even and even.next).
• Off-by-one: nodes are 1-indexed (first node is odd-indexed).
• Modifying next pointers in wrong order (creates cycles).

Interview preparation tip

Linked list rearrangement problems follow the "split and reconnect" pattern: maintain separate pointers for each group, build each group incrementally, then connect at the end. The evenHead saved reference is the critical piece — never lose it before reconnection. Practice similar problems: "separate positive and negative nodes," "group by k," "reverse alternate k nodes."