LeetCode 328: Odd Even Linked List Solution in Python – A Step-by-Step Guide

What Is LeetCode 328: Odd Even Linked List?

In LeetCode 328: Odd Even Linked List, you’re given the head of a singly linked list, and your task is to group all nodes with odd indices (1-based: 1st, 3rd, 5th, etc.) followed by all nodes with even indices (2nd, 4th, 6th, etc.), preserving their relative order within each group. For example, with 1->2->3->4->5, the result is 1->3->5->2->4. This problem tests your ability to manipulate linked list pointers, connecting to concepts in LeetCode 206: Reverse Linked List.

Problem Statement

• Input: Head of a singly linked list.
• Output: Head of the reordered list (odd indices then even indices).
• Rules:
• Indices are 1-based (1st node is odd).
• Maintain relative order within odd and even groups.
• Modify in-place if possible.

Constraints

• Number of nodes: 0 to 10⁴
• -10⁶ <= Node.val <= 10⁶

Examples

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

Understanding the Problem: Reordering the List

To solve LeetCode 328: Odd Even Linked List in Python, we need to split the list into odd-indexed and even-indexed nodes, then concatenate them, all while preserving order. A naive approach—copying to arrays and rebuilding—is O(n) time but O(n) space, missing the in-place goal. Instead, we’ll use:

• Best Solution (In-Place Pointers): O(n) time, O(1) space—fast and space-efficient.
• Alternative Solution (Two Lists): O(n) time, O(1) space (excluding recursion)—clear but less direct.

Let’s start with the in-place pointer solution, explained in a beginner-friendly way.

Best Solution: In-Place Pointers

Why This Is the Best Solution

The in-place pointer approach is the top choice for LeetCode 328 because it’s efficient—O(n) time, O(1) space—and manipulates the list directly with minimal overhead. It uses two pointers to separate odd and even nodes, then links them together, avoiding extra storage. It’s like choreographing a dance with the original lineup—smooth and clever!

How It Works

Think of this as a two-pointer dance:

• Step 1: Initialize Pointers:
• odd starts at head (1st node).
• even starts at head.next (2nd node).
• Save even_head for later linking.
• Step 2: Separate Nodes:
• Connect odd.next to the next odd node (skip even).
• Connect even.next to the next even node.
• Move pointers forward.
• Step 3: Concatenate:
• Link last odd node to even_head.
• Step 4: Why It Works:
• Maintains order within groups.
• In-place with pointer swaps.

It’s like splitting and rejoining a line in one pass!

Step-by-Step Example

Example: 1->2->3->4->5->NULL

• Init:
• odd = 1, even = 2, even_head = 2
• Step 1:
• odd.next = 3 (1->3), even.next = 4 (2->4)
• odd = 3, even = 4
• Step 2:
• odd.next = 5 (3->5), even.next = NULL (4->NULL)
• odd = 5, even = NULL
• Step 3:
• odd.next = even_head (5->2)
• Result: 1->3->5->2->4->NULL

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Handle empty or single-node cases
        if not head or not head.next:
            return head

        # Initialize pointers
        odd = head
        even = head.next
        even_head = even

        # Separate odd and even nodes
        while even and even.next:
            odd.next = even.next  # Link odd to next odd
            odd = odd.next        # Move odd forward
            even.next = odd.next  # Link even to next even
            even = even.next      # Move even forward

        # Concatenate odd and even lists
        odd.next = even_head
        return head

• Lines 3-4: Return if list is empty or has one node.
• Lines 7-9: Set odd to 1st, even to 2nd, save even start.
• Lines 12-16: While even nodes remain:
• Connect odd.next to next odd (skip even).
• Connect even.next to next even.
• Line 18: Link odd tail to even head.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(1)—just pointers.

This is like a linked list dance master—fast and sleek!

Alternative Solution: Two Lists Approach

Why an Alternative Approach?

The two-lists approach—O(n) time, O(1) space (excluding recursion)—splits the list into two separate lists (odd and even), then merges them. It’s more intuitive for visualizing the split but requires careful reconnection, making it a good learning tool. It’s like separating dancers into two groups before rejoining—clear but less direct!

How It Works

Split and merge:

• Step 1: Create two lists:
• Odd list for odd-indexed nodes.
• Even list for even-indexed nodes.
• Step 2: Traverse and assign nodes.
• Step 3: Connect odd tail to even head.

Step-by-Step Example

Example: 1->2->3->4->NULL

• Split:
• Odd: 1->3
• Even: 2->4
• Merge:
• 1->3->2->4
• Result: 1->3->2->4->NULL

Code for Two Lists Approach

Copy codeclass Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        # Initialize two lists
        odd_head = odd = head
        even_head = even = head.next

        # Split into odd and even lists
        curr = even.next
        is_odd = True
        while curr:
            if is_odd:
                odd.next = curr
                odd = curr
            else:
                even.next = curr
                even = curr
            curr = curr.next
            is_odd = not is_odd

        # Connect lists
        odd.next = even_head
        even.next = None
        return odd_head

• Time Complexity: O(n)—single pass.
• Space Complexity: O(1)—just pointers.

It’s a list-splitting organizer—vivid and steady!

Comparing the Two Solutions

• In-Place Pointers (Best):
• Pros: O(n) time, O(1) space, direct and efficient.
• Cons: Pointer logic trickier.
• Two Lists (Alternative):
• Pros: O(n) time, O(1) space, clearer split.
• Cons: More steps, slightly verbose.

In-place wins for elegance.

Additional Examples and Edge Cases

• [1]: 1->NULL.
• [1,2]: 1->2->NULL.
• []: NULL.

Both handle these perfectly.

Complexity Breakdown

• In-Place Pointers: Time O(n), Space O(1).
• Two Lists: Time O(n), Space O(1).

In-place is the leaner choice.

Key Takeaways

• In-Place Pointers: Dance in line—efficient!
• Two Lists: Split and join—clear!
• Python: Linked lists shine—see [Python Basics](/python/basics).
• Order: Indices guide the way.

Final Thoughts: Line Up the Nodes

LeetCode 328: Odd Even Linked List in Python is a linked list manipulation gem. The in-place pointer solution offers speed and elegance, while the two-lists approach provides a visual split. Want more list challenges? Try LeetCode 206: Reverse Linked List or LeetCode 445: Add Two Numbers II. Ready to reorder? Head to Solve LeetCode 328 on LeetCode and align those nodes today!