NUHMAN.com

Introduction

LeetCode 328: Odd Even Linked List is a classic linked list manipulation problem. The goal is to reorder the nodes of a linked list such that all odd-indexed nodes come before even-indexed nodes, maintaining the original relative order within each group.

This problem tests your skill in pointer manipulation, traversal logic, and clean in-place updates.

Problem Statement

Given a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices and return the reordered list.

The indexing starts at 1, so the first node is considered odd, the second even, and so on.

Example

python

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

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

✅ Approach: Two Pointers for Odd and Even

Step-by-Step Explanation

We use two pointers:

• odd: to track the tail of the odd-indexed list
• even: to track the tail of the even-indexed list
• even_head: to reconnect the even list after the odd list is done

Here's how we do it:

1. Initialize odd to the head and even to head.next.
2. Traverse the list:

• Link odd.next to even.next
• Move odd forward
• Link even.next to odd.next
• Move even forward

1. After traversal, connect the tail of the odd list to even_head

✅ Python Code

python

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

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        odd = head
        even = head.next
        even_head = even  # Save head of even list
        
        while even and even.next:
            odd.next = even.next
            odd = odd.next

            even.next = odd.next
            even = even.next
        
        odd.next = even_head  # Connect end of odd list to head of even list
        return head

🧪 Dry Run Example

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

• Step 1: odd = 1, even = 2
• Step 2: odd.next = 3, even.next = 4
• Step 3: odd.next = 5, even.next = None

Final list: 1 -> 3 -> 5 -> 2 -> 4

⏱️ Time & Space Complexity

MetricValueTime ComplexityO(n)Space ComplexityO(1)

🧠 Key Takeaways

• You can solve many linked list problems with two-pointer techniques.
• Separating the odd and even lists then combining them helps in reordering.
• Keep track of even_head to reconnect at the end.

🧱 Edge Cases

• Empty list → return None
• One or two nodes → return head as-is
• All odd or all even node counts

✅ Conclusion

LeetCode 328: Odd Even Linked List is a great problem to strengthen your confidence in in-place pointer manipulation. It’s clean, efficient, and has practical use in real-world linked list reordering.