LeetCode 328: Odd Even Linked List Solution

Master LeetCode problem 328 (Odd Even Linked List), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

328. Odd Even Linked List

Medium

Linked List

Problem Explanation

Explanation:

To solve this problem in O(1) extra space complexity and O(n) time complexity, we can reorganize the linked list by separating the odd-indexed nodes from the even-indexed nodes. We can achieve this by iterating through the original linked list and creating two separate lists for odd and even nodes. Finally, we merge these two lists to form the final reordered linked list.

Initialize two dummy nodes, oddDummy and evenDummy, to store the heads of the odd and even lists respectively.
Iterate through the original linked list, keeping track of the odd and even nodes separately.
At the end of the iteration, connect the last odd node to the first even node to form a single reordered linked list.
Return the head of the reordered linked list.

Time Complexity: O(n)
Space Complexity: O(1)

Solution Code

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode oddDummy = new ListNode(-1);
        ListNode evenDummy = new ListNode(-1);
        ListNode oddTail = oddDummy;
        ListNode evenTail = evenDummy;
        
        int index = 1;
        while (head != null) {
            if (index % 2 == 1) {
                oddTail.next = head;
                oddTail = oddTail.next;
            } else {
                evenTail.next = head;
                evenTail = evenTail.next;
            }
            head = head.next;
            index++;
        }
        
        oddTail.next = evenDummy.next;
        evenTail.next = null;
        
        return oddDummy.next;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 328 (Odd Even Linked List)?

This page provides optimized solutions for LeetCode problem 328 (Odd Even Linked List) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 328 (Odd Even Linked List)?

The time complexity for LeetCode 328 (Odd Even Linked List) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 328 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 328 in Java, C++, or Python.

Back to LeetCode Solutions