Difficulty: 🟡 Medium
Topics: Linked List

Solution

LeetCode 328 - Odd Even Linked List

Problem Understanding

This problem asks us to reorder a singly linked list so that all nodes located at odd indices appear first, followed by all nodes located at even indices.

The important detail is that the grouping is based on the node's position in the list, not the node's value. The first node is considered odd, the second node is even, the third node is odd again, and so on.

For example, given the list:

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

The nodes at odd positions are:

1, 3, 5

The nodes at even positions are:

2, 4

The final reordered list becomes:

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

The problem also requires that the relative order inside each group remains unchanged. This means that odd-indexed nodes must appear in the same order they originally appeared, and the same applies to even-indexed nodes.

The input is the head pointer of a singly linked list. The output should be the head of the modified list after reordering.

The constraints indicate that the linked list can contain up to 10^4 nodes. This immediately suggests that an O(n) solution is appropriate and expected. The problem also explicitly requires O(1) extra space, which means we cannot create additional arrays or linked lists proportional to the input size.

Several edge cases are important:

An empty list should simply return None.
A list with one node is already correctly ordered.
A list with two nodes is also already correctly ordered.
Lists with odd and even lengths must both work correctly.
Pointer manipulation mistakes can easily create cycles or disconnect parts of the list.

Because this is a linked list problem, careful handling of next pointers is the key challenge.

Approaches

Brute Force Approach

A straightforward solution is to traverse the linked list and store odd-positioned nodes and even-positioned nodes separately in auxiliary data structures such as arrays or separate linked lists.

We could:

Traverse the list while tracking the current position.
Append odd-positioned nodes to one list.
Append even-positioned nodes to another list.
Connect the odd list to the even list at the end.

This approach works because it explicitly separates nodes according to their positions while preserving their original order.

However, this method requires additional memory proportional to the number of nodes. Since the problem explicitly requires O(1) extra space, this solution violates the space constraint.

Optimal Approach

The key insight is that we do not need extra storage because the nodes already exist. We only need to rearrange the pointers.

We can maintain two running chains:

One chain for odd-indexed nodes
One chain for even-indexed nodes

As we traverse the list, we reconnect pointers so that:

Each odd node points to the next odd node
Each even node points to the next even node

At the end, we attach the even chain after the odd chain.

The important observation is that we can perform this re-linking in-place while traversing the list only once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Uses auxiliary storage to separate odd and even nodes
Optimal	O(n)	O(1)	Rearranges pointers in-place without extra storage

Algorithm Walkthrough

Handle trivial edge cases first.

If the list is empty or contains only one node, there is nothing to reorder. Return the head immediately. 2. Initialize pointers for the odd and even chains.

The first node is odd, so initialize:

odd = head

The second node is even, so initialize:

even = head.next

We also store:

even_head = even

This pointer is important because once we finish processing, we need to reconnect the odd chain to the beginning of the even chain. 3. Traverse the list while both odd and even nodes exist.

The loop condition is:

while even and even.next:

This ensures that there is always another odd node available. 4. Connect the current odd node to the next odd node.

Since even.next represents the next odd-positioned node:

odd.next = even.next

Then move the odd pointer forward:

odd = odd.next

Connect the current even node to the next even node.

After moving the odd pointer, the next even node becomes:

odd.next

So:

even.next = odd.next

Then move the even pointer forward:

even = even.next

Attach the even chain after the odd chain.

Once traversal is complete, all odd nodes are connected together and all even nodes are connected together.

We simply connect:

odd.next = even_head

Return the modified list head.

Why it works

The algorithm maintains two independent linked chains throughout execution:

The odd chain always contains all processed odd-positioned nodes in correct order.
The even chain always contains all processed even-positioned nodes in correct order.

Each iteration removes one odd node and one even node from the remaining unprocessed portion and appends them to their respective chains. Since nodes are processed in original order, the relative ordering is preserved. Finally, attaching the even chain after the odd chain produces the required arrangement.

Python Solution

# 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 not head or not head.next:
            return head

        odd = head
        even = head.next
        even_head = even

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

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

        odd.next = even_head

        return head

The implementation starts by handling empty and single-node lists. These cases do not require any reordering.

The odd pointer starts at the first node, while the even pointer starts at the second node. The even_head variable stores the start of the even chain so that it can later be attached after the odd chain.

Inside the loop, the algorithm first skips over the even node to connect the current odd node to the next odd node. Then it advances the odd pointer.

Next, it performs the same operation for the even chain by connecting the current even node to the next even node and advancing the even pointer.

The loop continues until there are no more even nodes or no next odd node available.

Finally, the tail of the odd chain is connected to the head of the even chain, completing the reordered list.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func oddEvenList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    odd := head
    even := head.Next
    evenHead := even

    for even != nil && even.Next != nil {
        odd.Next = even.Next
        odd = odd.Next

        even.Next = odd.Next
        even = even.Next
    }

    odd.Next = evenHead

    return head
}

The Go implementation follows the same logic as the Python solution. The primary difference is Go's explicit use of nil instead of Python's None.

Pointer manipulation behaves similarly in both languages because linked lists naturally rely on references. No additional memory allocation is required, which satisfies the O(1) space requirement.

Worked Examples

Example 1

Input:

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

Initial state:

Variable	Value
odd	1
even	2
even_head	2

Iteration 1

Connect odd nodes:

1 -> 3

Move odd:

Variable	Value
odd	3

Connect even nodes:

2 -> 4

Move even:

Variable	Value
even	4

Current structure:

Odd chain: 1 -> 3
Even chain: 2 -> 4
Remaining: 5

Iteration 2

Connect odd nodes:

3 -> 5

Move odd:

Variable	Value
odd	5

Connect even nodes:

4 -> None

Move even:

Variable	Value
even	None

Current structure:

Odd chain: 1 -> 3 -> 5
Even chain: 2 -> 4

Attach even chain:

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

Final output:

[1,3,5,2,4]

Example 2

Input:

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

Initial state:

Variable	Value
odd	2
even	1

Iteration 1

After processing:

Odd chain: 2 -> 3
Even chain: 1 -> 5

Pointers:

Variable	Value
odd	3
even	5

Iteration 2

After processing:

Odd chain: 2 -> 3 -> 6
Even chain: 1 -> 5 -> 4

Pointers:

Variable	Value
odd	6
even	4

Iteration 3

After processing:

Odd chain: 2 -> 3 -> 6 -> 7
Even chain: 1 -> 5 -> 4

Pointers:

Variable	Value
odd	7
even	None

Attach even chain:

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

Final output:

[2,3,6,7,1,5,4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited and relinked at most once
Space	O(1)	Only a few pointer variables are used

The algorithm performs a single traversal of the linked list. Each iteration processes one odd node and one even node, so the total work is proportional to the number of nodes.

No extra arrays, stacks, or hash maps are allocated. Only a constant number of pointers are maintained, which satisfies the O(1) auxiliary space requirement.

Test Cases

# Helper utilities for testing

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

def build_list(values):
    dummy = ListNode()
    current = dummy

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

    return dummy.next

def to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

solution = Solution()

# Example 1
head = build_list([1, 2, 3, 4, 5])
assert to_list(solution.oddEvenList(head)) == [1, 3, 5, 2, 4]  # standard odd length case

# Example 2
head = build_list([2, 1, 3, 5, 6, 4, 7])
assert to_list(solution.oddEvenList(head)) == [2, 3, 6, 7, 1, 5, 4]  # mixed values with odd length

# Empty list
head = build_list([])
assert to_list(solution.oddEvenList(head)) == []  # empty input

# Single node
head = build_list([1])
assert to_list(solution.oddEvenList(head)) == [1]  # one node only

# Two nodes
head = build_list([1, 2])
assert to_list(solution.oddEvenList(head)) == [1, 2]  # already correctly ordered

# Even number of nodes
head = build_list([1, 2, 3, 4, 5, 6])
assert to_list(solution.oddEvenList(head)) == [1, 3, 5, 2, 4, 6]  # even length list

# All identical values
head = build_list([7, 7, 7, 7])
assert to_list(solution.oddEvenList(head)) == [7, 7, 7, 7]  # duplicates should preserve structure

# Three nodes
head = build_list([1, 2, 3])
assert to_list(solution.oddEvenList(head)) == [1, 3, 2]  # smallest meaningful reordering case

# Longer list
head = build_list([1, 2, 3, 4, 5, 6, 7, 8, 9])
assert to_list(solution.oddEvenList(head)) == [1, 3, 5, 7, 9, 2, 4, 6, 8]  # stress ordering preservation

Test	Why
`[1,2,3,4,5]`	Validates standard odd-length behavior
`[2,1,3,5,6,4,7]`	Confirms correct ordering preservation
`[]`	Ensures empty lists are handled safely
`[1]`	Verifies single-node edge case
`[1,2]`	Verifies two-node edge case
`[1,2,3,4,5,6]`	Tests even-length lists
`[7,7,7,7]`	Ensures logic depends on positions, not values
`[1,2,3]`	Smallest non-trivial rearrangement
`[1,2,3,4,5,6,7,8,9]`	Stress test for pointer correctness

Edge Cases

Empty List

An empty list is represented by head = None. This case can easily cause null pointer access errors if the implementation immediately attempts to read head.next.

The solution avoids this problem with the initial guard clause:

if not head or not head.next:
    return head

This ensures safe handling before any pointer manipulation begins.

Single Node List

A list containing only one node is already correctly ordered because the single node is at an odd position.

A buggy implementation might incorrectly attempt to access or modify nonexistent even nodes. The same initial guard clause safely handles this scenario and immediately returns the original list.

Even Length Lists

Lists with an even number of nodes can expose pointer update mistakes. For example:

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

If the loop condition is incorrect, the implementation might attempt to access even.next when even is already None.

The condition:

while even and even.next:

ensures that every pointer access remains valid and prevents runtime errors.

Preserving Relative Order

The problem requires preserving the original relative ordering inside the odd and even groups.

A naive implementation that inserts nodes at the front of temporary lists would reverse the order accidentally.

This solution always appends nodes sequentially by relinking pointers in traversal order, guaranteeing stable ordering within both groups.