328. Odd Even Linked List

Medium · solved 2026-10-05 · Open on LeetCode

linked-list

Time O(n) · Space O(1)

How to get there

Two chains grown side by side

1. Restate what moves. Positions decide the order, not values: positions 1, 3, 5, … first, then 2, 4, 6, …, each group in its original order. With O(1) extra space, the nodes have to be relinked where they are, not copied.

2. Sort [1, 2, 3, 4, 5] by hand and find where one pass gets stuck. Walking left to right, each node joins one of two chains: 1, 3, 5 to the odd chain, 2, 4 to the even chain. But the even chain goes after the whole odd chain, and its first node, the 2, was passed near the start. By the time the odd chain is done, the walk can’t go back for it.

3. Find what to remember. The head of the even chain, even_start, so it can be attached at the end. And the tail of each chain, since that is where its next node is added. The odd chain’s head is head itself.

4. See where each chain’s next node is. The positions alternate, so the node right after the even tail is the next odd node, and the node right after the new odd tail is the next even node. Two tail pointers, each one step ahead of the other, are all the walk needs.

5. Join the chains at the end. When the nodes run out, link the odd tail to even_start. The even tail already points to None, because it was copied from the end of the list.

6. Check the cost. Each node is relinked once: O(n) time, and three pointers: O(1) space.

The reusable recipe: to split a list into interleaved groups in place, keep a tail pointer per group and give each node to the group whose turn it is. Remember the head of every group but the first, to stitch them together at the end.

Let the tails' meanings fix the order

Variable	Always means, at the top of the loop
`odd`	the tail of the odd chain
`even`	the tail of the even chain, or `None` once the nodes run out
`even_start`	the head of the even chain
`odd.next`	`even`: the odd tail is still linked to the even tail that follows it

Code	What happened	What it keeps true
`if not head: return head`	the list is empty	the empty list is the answer, and `head.next` below is safe
`odd, even = head, head.next`	positions 1 and 2 start the two chains	each chain has its first node as its tail
`while even and even.next:`	a node follows the even tail	that node is the next odd one
`odd.next = even.next`, `odd = odd.next`	the next odd node joins the odd chain	`odd` is its new tail
`even.next = odd.next`, `even = even.next`	the node after it, or `None`, joins the even chain	`even` is its new tail, so `odd.next` is `even` again
`odd.next = even_start`	the nodes ran out	the even chain goes after the odd chain

Why odd moves first. The last row of the first table is the one that decides the order. While odd.next is even, the next even node isn’t reachable through odd yet. Linking even.next = odd.next at that point links even to itself: attempt-1.py does this, so the loop never ends. Saving tmp = odd.next before odd moves saves the even tail instead of the next even node, so the even chain falls one node behind and loses the last node on even lengths, as in attempt-3.py. Moving odd first makes odd.next the next even node, which is exactly what even needs.

Where the loop stops. On an odd length, even becomes None and odd is the last node. On an even length, even is the last node and even.next is None. Either way the even chain already ends in None, so odd.next = even_start is the only link left.

The method carries over: write down what each pointer means, including how the pointers relate to each other, and order the updates so that relation is true whenever the next update reads it.

Alternatives compared

Approach	Time	Space	How it works
Copy the values into two lists	O(n)	O(n)	Collect the odd-position and even-position values, then write them back in order.
Two dummy heads	O(n)	O(1)	Walk with a position counter and append each node to an odd or even dummy chain, then join the chains and end the even one with `None`.
Odd and even tails (chosen, `solution-2-clean.py`)	O(n)	O(1)	Grow both chains together: the node after the even tail joins the odd chain, and the node after the new odd tail joins the even chain.
Odd and even tails with extra guards (`solution-1-original.py`)	O(n)	O(1)	The same relinking, checking for an empty list in the loop condition and before the final link, and setting `even.next = None`, which is already `None`.

The problem statement asks for O(1) extra space, which rules out the copy. The dummy heads need a counter and a branch per node, while the tails approach handles one odd and one even node per turn with no branch.

attempt-1.py

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

        odd = head
        even = head.next if head.next else head
        even_start = even

        while odd.next and odd.next.next:
            even.next = odd.next
            even = even.next

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

        odd.next = even_start

        return head

attempt-2.py

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

        odd = head
        even = head.next if head.next else head
        even_start = even

        while odd.next and odd.next.next:
            tmp = odd.next

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

            even.next = tmp
            even = even.next

        even.next = None
        print(odd.next)
        print(even_start)
        #odd.next = even_start

        return head

attempt-3.py

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

        odd = head
        even = head.next if head else None
        even_start = even

        while odd.next and odd.next.next:
            tmp = odd.next

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

            even.next = tmp
            even = even.next

        if even:
            even.next = None
        odd.next = even_start

        return head

solution-1-original.py

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

        odd = head
        even = head.next if head else None
        even_start = even

        while odd and odd.next and odd.next.next:

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

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

        if even:
            even.next = None
        if odd:
            odd.next = even_start

        return head

solution-2-clean.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode | None) -> ListNode | None:
        if not head:
            return head

        odd, even = head, head.next
        even_start = even
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next

        odd.next = even_start
        return head

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.