Odd Even Linked List – LeetCode75 Python Solution Explained

Linked lists are fundamental data structures in computer science, and manipulating their nodes efficiently is a key skill for coding interviews and software development. The Odd Even Linked List problem (LeetCode75) is a classic exercise that tests your understanding of linked list traversal, pointer manipulation and node reordering.

In this blog, we’ll break down the problem, explore examples, provide a complete Python solution, explain the logic step by step and analyze its complexity. By the end, you’ll have a solid understanding of how to rearrange linked lists while maintaining O(1) space and O(n) time efficiency.

Problem Statement

Given a singly linked list, group all odd-positioned nodes together followed by even-positioned nodes.

Note that the node position starts at 1 (head is odd).
You must preserve the relative order of odd and even nodes.
The solution should use O(1) extra space and run in O(n) time.

Input: head = [1, 2, 3, 4, 5]
Output: [1, 3, 5, 2, 4]

Understanding the Problem

The problem requires separating nodes based on their positions (odd or even) rather than their values. After separation, we reconnect the odd list to the even list.

Key observations:

The first node is odd, the second node is even.
Odd nodes are linked sequentially, even nodes are linked sequentially.
After processing all nodes, link the tail of odd nodes to the head of even nodes.

This problem is ideal for practicing pointer manipulation and in-place reordering of a linked list.

Examples

Example 1

Input: [1, 2, 3, 4, 5]
Output: [1, 3, 5, 2, 4]

Example 2

Input: [2, 1, 3, 5, 6, 4, 7]
Output: [2, 3, 6, 7, 1, 5, 4]

Example 3

Input: [1]
Output: [1]

Complete Python Solution

from typing import Optional

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        odd_head = head
        even_head = head.next
        odd_tail = odd_head
        even_tail = even_head

        while even_tail and even_tail.next:
            # Connect the next odd node
            odd_tail.next = even_tail.next
            odd_tail = odd_tail.next

            # Connect the next even node
            even_tail.next = odd_tail.next
            even_tail = even_tail.next

        # Connect odd list to even list
        odd_tail.next = even_head

        return odd_head

    def printLinkedList(head):
        current = head
        while current:
            print(current.val, end=" -> ")
            current = current.next
        print("None")

Step-by-Step Explanation

Step 1: Handle Edge Cases

If the list is empty or contains only one node, return the head directly.

if not head or not head.next:
    return head

Step 2: Initialize Pointers

Create pointers for odd and even heads and their tails.

odd_head = head
even_head = head.next
odd_tail = odd_head
even_tail = even_head

Step 3: Reorder Nodes

Traverse the list while connecting the next odd node after odd_tail and the next even node after even_tail.

while even_tail and even_tail.next:
    odd_tail.next = even_tail.next
    odd_tail = odd_tail.next

    even_tail.next = odd_tail.next
    even_tail = even_tail.next

Step 4: Connect Odd and Even Lists

After the traversal, link the end of the odd list to the head of the even list.

odd_tail.next = even_head

Step 5: Return the Head

Return odd_head as the head of the modified list.

return odd_head

Time and Space Complexity

Time Complexity: O(n) → Each node is visited once.
Space Complexity: O(1) → No extra memory is used besides pointers.

Edge Cases

Empty list → Return None.
Single-node list → Return the node itself.
Two-node list → Only swap if necessary.

Real-World Applications

The Odd Even Linked List problem models scenarios such as:

Task scheduling where tasks are executed in alternating priorities.
Reordering queues in systems to optimize processing.
Memory-efficient data manipulation without using extra space.
Simulation of alternating events in games or network systems.

Conclusion

The Odd Even Linked List problem (LeetCode75) is an excellent exercise to master pointer manipulation and in-place linked list reordering. By separating nodes into odd and even positions and reconnecting them, we achieve a clean, efficient solution with minimal memory usage.

Practicing this problem enhances your understanding of linked lists, prepares you for coding interviews and improves your ability to implement real-world data structure operations efficiently.