Odd Even Linked List (LeetCode 328)

The problem

You get the head of a linked list. Reorder it so all nodes at odd positions (1st, 3rd, 5th, …) come first, followed by all nodes at even positions. Within each group, keep the original relative order. Positions are about where a node sits, not its value. Do it in O(1) extra space and O(n) time.

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 3 -> 5 -> 2 -> 4

Positions 1, 3, 5 hold 1, 3, 5; positions 2, 4 hold 2, 4.

How to think about it

Start with brute force. Walk the list, appending odd-position nodes to one array and even-position nodes to another, then relink them. O(n) time, but O(n) extra space, which the problem forbids.

The key insight: the list already contains both chains, interleaved. Odd nodes are every other node starting at the head; even nodes are every other node starting at head.next. You can unzip them in place: each odd node should point to the node two steps ahead (the next odd), and so should each even node. Two pointers, odd and even, leapfrog each other down the list doing exactly that.

Remember where the even chain starts. Once the weave is done, the odd chain ends at its last node and the even chain is detached. Save evenHead = head.next at the start, then finish with odd.next = evenHead.

Which pattern is this? Linked-list pointer rewiring with two runners. The tell is “rearrange by position, in place, O(1) space”.

Approach

1. If the list is empty, return None.
2. Set odd = head, even = head.next, and save evenHead = even.
3. While even and even.next exist:
   • odd.next = even.next, then move odd forward,
   • even.next = odd.next, then move even forward.
4. Join the chains: odd.next = evenHead.
5. Return head.

Solution

def odd_even_list(head):
    if not head: return None
    odd = head; even = head.next; evenHead = even # save where the even chain starts
    while even and even.next:
        odd.next = even.next; odd = odd.next      # odd skips over one even node
        even.next = odd.next; even = even.next    # even skips over one odd node
    odd.next = evenHead                           # stitch evens after the last odd
    return head
# odd_even_list([1,2,3,4,5]) -> [1,3,5,2,4]

Dry run

On 1 -> 2 -> 3 -> 4 -> 5. Start: odd = 1, even = 2, evenHead = 2.

even is None, so the loop stops. Joining gives 1 -> 3 -> 5 -> 2 -> 4.

Complexity

• Time: O(n). Each iteration advances both pointers by one node; together they cover the list once.
• Space: O(1). Three pointers. Nodes are re-linked, not copied.

Edge cases and pitfalls

• Empty list: returns None from the first line.
• One or two nodes: the loop never runs; odd.next = evenHead leaves the list as it was.
• Even length ([1,2,3,4] gives [1,3,2,4]): the loop ends with even on the last node, whose next is already None, so the even chain is properly terminated.
• Forgetting evenHead. Once the weave starts, head.next points to 3, so you can no longer find the start of the even chain.
• Sorting by value parity. “Odd” means position, not val % 2.

Related problems

• Swap Nodes in Pairs (LeetCode 24): another position-based rearrangement done with pointer writes.
• Reorder List (LeetCode 143): the reverse operation in spirit, weaving two halves together.
• Middle of the Linked List (LeetCode 876): two pointers again, here moving at different speeds.