LeetCode 328: Odd Even Linked List

Problem Restatement

We are given the head of a singly linked list.

We need to reorder the list so that all nodes at odd positions come first, followed by all nodes at even positions.

The position is 1-indexed:

1st node -> odd
2nd node -> even
3rd node -> odd
4th node -> even

This is about node positions, not node values.

The relative order inside each group must stay the same.

For example:

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

The odd-position nodes are:

1, 3, 5

The even-position nodes are:

2, 4

So the final list is:

1 -> 3 -> 5 -> 2 -> 4

The problem requires O(n) time and O(1) extra space. We must rearrange the existing nodes by changing next pointers.

Input and Output

Function shape:

def oddEvenList(head: Optional[ListNode]) -> Optional[ListNode]:
    ...

Examples

Example 1:

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

Odd-position nodes:

1 -> 3 -> 5

Even-position nodes:

2 -> 4

Connect odd list to even list:

1 -> 3 -> 5 -> 2 -> 4

Example 2:

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

Odd-position nodes:

2 -> 3 -> 6 -> 7

Even-position nodes:

1 -> 5 -> 4

Final list:

2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4

First Thought: Build Two Lists

A simple idea is to traverse the original linked list and place nodes into two separate lists:

1. One list for odd-position nodes.
2. One list for even-position nodes.

Then connect the odd list to the even list.

This idea is correct, but creating new nodes would use extra space. The problem asks for O(1) extra space, so we should reuse the original nodes.

We can still use the same idea, but instead of creating new lists, we rewire the next pointers in place.

Key Insight

Keep two chains while walking through the list:

At the start:

1 -> 2 -> 3 -> 4 -> 5
^    ^
odd  even

even_head points to node 2, because we need to attach the even chain after the odd chain at the end.

The pointer rewiring works like this:

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

This connects the current odd node to the next odd-position node.

Then:

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

This connects the current even node to the next even-position node.

At the end:

odd.next = even_head

This places all even-position nodes after all odd-position nodes.

Algorithm

Handle small lists first.

If the list is empty or has only one node, return it as-is.

Otherwise:

1. Set odd = head.
2. Set even = head.next.
3. Save even_head = even.
4. While even and even.next both exist:
   1. Link odd.next to even.next.
   2. Move odd forward.
   3. Link even.next to odd.next.
   4. Move even forward.
5. Link the end of the odd chain to even_head.
6. Return head.

Walkthrough

Take:

1 -> 2 -> 3 -> 4 -> 5

Initial state:

odd = 1
even = 2
even_head = 2

First loop:

odd.next = even.next

This links 1 to 3.

1 -> 3 -> 4 -> 5
2 -> 3 -> 4 -> 5

Move odd to 3.

Then:

even.next = odd.next

This links 2 to 4.

Now we have:

odd chain:  1 -> 3 -> 4 -> 5
even chain: 2 -> 4 -> 5

Second loop:

Link 3 to 5.

Link 4 to None.

Now:

odd chain:  1 -> 3 -> 5
even chain: 2 -> 4

Finally connect:

5.next = 2

Final result:

1 -> 3 -> 5 -> 2 -> 4

Correctness

The algorithm maintains two chains.

The odd chain contains the nodes at positions 1, 3, 5, ... that have already been processed.

The even chain contains the nodes at positions 2, 4, 6, ... that have already been processed.

At each loop step, even.next is the next odd-position node. Assigning:

odd.next = even.next

adds that node to the odd chain.

Then odd.next is the next even-position node. Assigning:

even.next = odd.next

adds that node to the even chain.

The order inside each chain stays unchanged because we always append the next odd node to the odd chain and the next even node to the even chain.

When the loop ends, all nodes have been assigned to exactly one of the two chains. Connecting:

odd.next = even_head

places the complete even chain after the complete odd chain.

Therefore, the returned list has all odd-position nodes first, then all even-position nodes, while preserving relative order inside both groups.

Complexity

Implementation

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional

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

        odd = head
        even = head.next
        even_head = even

        while even is not None and even.next is not None:
            odd.next = even.next
            odd = odd.next

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

        odd.next = even_head

        return head

Code Explanation

Start with the first odd-position node:

odd = head

Start with the first even-position node:

even = head.next

Save the first even node:

even_head = even

We need this later because after the odd chain is complete, we attach the even chain to its end.

The loop condition is:

while even is not None and even.next is not None:

This means there is still another odd-position node after the current even node.

Move the next odd node into the odd chain:

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

Move the next even node into the even chain:

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

After the loop, connect the two chains:

odd.next = even_head

Finally, return the original head:

return head

The head stays the same because the first node remains the first node in the reordered list.

Testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode(0)
    tail = dummy

    for value in values:
        tail.next = ListNode(value)
        tail = tail.next

    return dummy.next

def to_list(head):
    values = []

    while head is not None:
        values.append(head.val)
        head = head.next

    return values

def run_tests():
    s = Solution()

    head = build_list([1, 2, 3, 4, 5])
    assert to_list(s.oddEvenList(head)) == [1, 3, 5, 2, 4]

    head = build_list([2, 1, 3, 5, 6, 4, 7])
    assert to_list(s.oddEvenList(head)) == [2, 3, 6, 7, 1, 5, 4]

    head = build_list([])
    assert to_list(s.oddEvenList(head)) == []

    head = build_list([1])
    assert to_list(s.oddEvenList(head)) == [1]

    head = build_list([1, 2])
    assert to_list(s.oddEvenList(head)) == [1, 2]

    head = build_list([1, 2, 3])
    assert to_list(s.oddEvenList(head)) == [1, 3, 2]

    print("all tests passed")

run_tests()

Test meaning: