328. Odd Even Linked List

Reformulated question¶

Reorder a singly linked list so that all nodes in odd positions come first, followed by all nodes in even positions, while keeping the original relative order inside each group.

Position starts at 1.
Do it in \(O(n)\) time and \(O(1)\) extra space.

Example:

input:  1 -> 2 -> 3 -> 4 -> 5
output: 1 -> 3 -> 5 -> 2 -> 4
state:  odds = [1, 3, 5], evens = [2, 4]

Key trick¶

Use two pointers, one walking odd nodes and one walking even nodes, and remember the start of the even list so you can append it at the end.

Trap¶

The common mistake is rebuilding the list with extra arrays or breaking the original order.

Another trap is forgetting to stop when even or even.next becomes None.

Why is this question interesting?¶

It tests pointer manipulation, in-place list rewiring, and careful handling of list invariants under \(O(1)\) extra space.

Solution¶

from typing import Optional
from utils import ListNode


class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Empty list or one node is already valid.
        if head is None or head.next is None:
            return head

        odd = head
        even = head.next
        even_head = even

        # Rewire pointers in-place:
        # odd -> next odd
        # even -> next even
        while even and even.next:
            odd.next = even.next
            odd = odd.next

            even.next = odd.next
            even = even.next

        # Append even list after odd list.
        odd.next = even_head
        return head

Pytest test¶

import pytest

from utils import list_build, list_to_python_list


@pytest.mark.parametrize(
    "values, expected",
    [
        ([], []),
        ([1], [1]),
        ([1, 2], [1, 2]),
        ([1, 2, 3], [1, 3, 2]),
        ([1, 2, 3, 4, 5], [1, 3, 5, 2, 4]),
        ([2, 1, 3, 5, 6, 4, 7], [2, 3, 6, 7, 1, 5, 4]),
        ([10, 20, 30, 40, 50, 60], [10, 30, 50, 20, 40, 60]),
    ],
)
def test_odd_even_list(values, expected):
    head = list_build(values)
    result = Solution().oddEvenList(head)
    assert list_to_python_list(result) == expected

Comment on your solution¶

Your solution is correct in spirit and meets the required complexity.

It keeps the odd and even chains in order.
It uses \(O(1)\) extra space.
The loop condition is right.

One thing to simplify is the pointer update logic:

odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next

This is easier to read than introducing next_odd and next_even plus temporary rewiring inside the loop.

## Solution
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head

        # |1| -> head|2| -> 3
        # 1 -> |3| -> 2 -> |None|
        #
        # |1| -> head|2| -> 3 -> 4
        # 1 -> |3| -> 2 -> |4|
        #
        # |1| -> 2 -> |3| -> 4 -> 5
        # 1 -> |3| -> head|2| -> |4| -> 5
        # 1 -> 3 -> |5| -> head|2| -> 4 -> |None|
        odd = head
        even = head.next
        even_head = even

        while even and even.next:
            next_odd = even.next
            next_even = even.next.next
            odd.next = next_odd
            odd.next.next = even_head
            even.next = next_even
            odd = odd.next
            even = even.next
        return head