Odd Even Linked List LeetCode 328 Guide

LeetCode 328 — Odd Even Linked List — asks you to rearrange a singly linked list so that all nodes at odd index positions come first, followed by all nodes at even index positions. The first node is at index 1 (odd), the second at index 2 (even), and so on. You must return the reordered list head.

The problem is labeled Medium and is a staple in linked list interview rounds because it tests in-place pointer manipulation without extra space. The naive approach of collecting values into arrays and rewriting the list is not acceptable — the problem requires O(1) extra space.

Key constraints to keep in mind: the list can have 0 to 10,000 nodes, node values are between -1,000,000 and 1,000,000, and you must achieve O(n) time and O(1) space.

The key insight is to maintain two separate pointer chains as you traverse: an odd chain collecting nodes at positions 1, 3, 5, ... and an even chain collecting nodes at positions 2, 4, 6, ... Each pointer advances two steps at a time, naturally skipping every other node.

At the end of traversal, connect the tail of the odd chain to the head of the even chain. This single pointer update joins the two groups into the correctly reordered list. The entire operation touches each node exactly once and uses only a constant number of extra pointers.

This strategy is clean because you never move or copy node values — you only redirect the next pointers. The relative order within each group (odd-indexed nodes among themselves, even-indexed nodes among themselves) is preserved.

Initialize odd to head and even to head.next. Save evenHead = even — this reference will be used at the end to connect the two chains. The loop continues while even and even.next are both non-null; when either is null all nodes have been assigned.

Inside each loop iteration, four pointer updates happen: odd.next = even.next advances odd to pick up the next odd-indexed node, then odd = odd.next advances the odd pointer forward. Then even.next = odd.next picks up the next even-indexed node, and even = even.next advances the even pointer forward.

After the loop, connect the chains with odd.next = evenHead. This appends the entire even chain after the last odd-indexed node. Return head — the original head is still the first odd-indexed node and remains the correct list head.

The odd and even pointers alternate through the list, each skipping one node per iteration. The odd pointer steps over even-indexed nodes to land on the next odd-indexed node; the even pointer steps over odd-indexed nodes to land on the next even-indexed node. This naturally separates the two groups without any extra data structure.

No new nodes are created and no values are copied. Only the next pointers are redirected. Because each node is visited exactly once, the algorithm runs in O(n) time. Because only a fixed number of pointer variables are used (odd, even, evenHead), the space complexity is O(1).

The loop termination condition — while even and even.next are not null — is carefully chosen. It handles both even-length and odd-length lists: for odd-length lists, the last node is odd-indexed and even will reach null after the final iteration; for even-length lists, even will reach the last node and even.next will be null.

Trace through the list 1 → 2 → 3 → 4 → 5. Odd-indexed nodes are 1 (pos 1), 3 (pos 3), 5 (pos 5). Even-indexed nodes are 2 (pos 2), 4 (pos 4). After reordering the result should be 1 → 3 → 5 → 2 → 4.

Start: odd = node 1, even = node 2, evenHead = node 2. Iteration 1: odd.next = node 3, odd advances to node 3; even.next = node 4, even advances to node 4. Iteration 2: odd.next = node 5, odd advances to node 5; even.next = null (node 5 has no next), even advances to null — loop ends.

After the loop: odd = node 5, odd.next = evenHead (node 2). The odd chain is 1 → 3 → 5 and the even chain is 2 → 4 → null. After connecting: 1 → 3 → 5 → 2 → 4 → null. Return head = node 1.

In Python: guard against an empty list or single-node list by returning head early if not head or not head.next. Set odd = head, even = head.next, evenHead = even. Enter the while loop, perform the four pointer updates each iteration, then connect odd.next = evenHead and return head. Core logic is 8 lines.

In Java: the structure is identical. Use a null check at the top, initialize the three pointers, run the while loop with the same four updates, connect the chains, and return head. The ListNode class is provided by the judge — no extra imports needed. Time O(n), space O(1).

Both solutions handle edge cases naturally: an empty list returns null via the early guard, a single-node list returns head via the early guard, and a two-node list runs zero iterations of the loop then connects odd.next = evenHead directly.

Odd Even Linked List belongs to a family of in-place linked list reordering problems. Reorder List (LeetCode 143) requires finding the midpoint, reversing the second half, then interleaving — it combines three linked list sub-skills. Remove Nth Node From End (LeetCode 19) uses two pointers with a deliberate gap to remove a node in one pass.

Reverse Linked List II (LeetCode 92) reverses a sublist between indices left and right, requiring precise pointer surgery at the boundaries. Partition List (LeetCode 86) partitions a list around a value x, keeping relative order — structurally very similar to the two-chain approach used here.

The common theme across this family is avoiding extra data structures by redirecting next pointers directly. Once you internalize the pattern of maintaining separate chains or using pointer gaps, the entire linked list reordering category becomes approachable.