Odd Even Linked List Solution

Problem

Given a singly linked list, rearrange it so that all nodes at odd positions appear first, followed by all nodes at even positions. Positions are 1-indexed — the first node is at position 1, the second at position 2, and so on. The relative order within each group must be preserved.

→

→∅

[1,2,3,4,5]

Input: head = [1, 2, 3, 4, 5]
Output: [1, 3, 5, 2, 4]
Explanation: Nodes at positions 1, 3, 5 (values 1, 3, 5) come first, then nodes at positions 2, 4 (values 2, 4).

A counter-example: [2, 1, 3, 5, 6, 4, 7] → [2, 3, 6, 7, 1, 5, 4]. Notice that the node with value 2 (at position 1) stays in the "odd" group even though 2 is an even number — it's the position, not the value, that determines the group.

Intuition

The problem asks you to interleave two sequences — odd-indexed and even-indexed nodes — back-to-back. The key insight is that you never actually need to move nodes to new memory: you can maintain two running tails simultaneously, advancing each by two steps on every iteration, then stitch the chains together once. The only bookkeeping required is saving a reference to where the even sublist starts before any pointers are modified.

Approach 1 — Collect and Rebuild

Walk the list once, separating node values by index parity into two arrays, then overwrite the original list nodes with values in the new order.

Walk the list with an index counter, appending each node's value to either odd_values or even_values based on whether the index is odd or even.
Walk the list a second time, overwriting each node's value from the concatenated odd_values + even_values array.
Return the original head (structure unchanged, values reordered).

1def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
2    if not head:
3        return head
4
5    odd_values = []
6    even_values = []
7    current = head
8    index = 1
9    while current:
10        if index % 2 == 1:
11            odd_values.append(current.val)
12        else:
13            even_values.append(current.val)
14        current = current.next
15        index += 1
16
17    current = head
18    for val in odd_values + even_values:
19        current.val = val
20        current = current.next
21
22    return head

Time: O(n) — two full passes through the list
Space: O(n) — two arrays that together hold every node's value

Approach 2 — In-Place Two Pointers

Maintain two running tails — odd for the odd-indexed sublist and even for the even-indexed sublist — advancing both by two positions each iteration, then connect the odd tail to the saved even head.

Save even_head = head.next immediately — this is the entry point to the even sublist and must be captured before any pointer is modified.
Set odd = head and even = head.next as the current tails of each sublist.
While even and even.next are both non-null:
- Link odd.next to even.next (the next odd-indexed node).
- Advance odd to odd.next.
- Link even.next to odd.next (the next even-indexed node).
- Advance even to even.next.
Set odd.next = even_head to attach the complete even sublist after the odd sublist.
Return the original head.

1def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
2    if not head:
3        return head
4
5    odd = head          # running tail of the odd-indexed sublist
6    even = head.next    # running tail of the even-indexed sublist
7    even_head = even    # save even list entry; needed to reconnect at the end
8
9    while even and even.next:
10        odd.next = even.next    # skip over even node to reach the next odd node
11        odd = odd.next          # advance odd tail forward by two positions
12        even.next = odd.next    # skip over odd node to reach the next even node
13        even = even.next        # advance even tail forward by two positions
14
15    odd.next = even_head    # attach the complete even sublist after the odd sublist
16    return head

Time: O(n) — single pass; each node is touched exactly once
Space: O(1) — only three extra pointers regardless of list length

Complexity Summary

Approach	Time	Space	When to use
Collect and Rebuild	O(n)	O(n)	When clarity matters more than memory and you're allowed to copy values
In-Place Two Pointers	O(n)	O(1)	Preferred; whenever pointer-level rearrangement is required

Common Mistakes

Forgetting to save even_head before modifying pointers — the first line inside the loop re-links odd.next away from the even sublist, so if you didn't capture even_head first, you've permanently lost the entry point to the even chain.
Loop condition missing even.next — writing while even: instead of while even and even.next: causes a null dereference when accessing even.next inside the loop on any list with an even number of elements, where the final even node has no successor.
Swapping the order of assignments inside the loop — you must assign odd.next = even.next and then advance odd before assigning even.next = odd.next; reversing this causes even.next to point to the same node as the old even, breaking the even chain.
Confusing node index parity with node value parity — the problem groups nodes by their 1-based position (odd position vs. even position), not by whether the stored value is odd or even. A node with value 4 at position 1 belongs in the odd sublist.
Returning odd or even instead of head — the first node never moves from its position in memory; only its next pointer changes. Always return the original head.

Odd Even Linked List — Solution