Odd Even Linked List Leetcode Solution

Problem Statement

The Odd-Even Linked List LeetCode Solution – “Odd-Even Linked List” states that given a non-empty singly linked list. We need to group all nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

Example:

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

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

Explanation:

• Nodes present at odd indices are: [1, 3, 5].
• Nodes present at even indices are: [2, 4].
• On Grouping the above two sets: [1, 3, 5, 2, 4].

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

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

Explanation:

• Nodes present at odd indices are: [2, 3, 6, 7].
• Nodes present at even indices are: [1, 5, 4].
• On Grouping the above two sets: [2, 3, 6, 7, 1, 5, 4].

Approach

Idea:

1. The main idea to solve this problem is to use simple traversal in the linked lists.
2. Traverse through the linked list and maintain a variable that keeps track of whether the current node is at an odd index or even index.
3. If the current node is at an odd index, assign it as the next node of the odd linked list.
4. If the current node is at an even index, assign it as the next node of the even linked list.
5. Finally, a head node of the even linked list is the next node at the end of the odd linked list, hence grouping odd and even indices together.
6. Return the head of the newly grouped linked list as our answer.

Code

Odd-Even Linked List Leetcode C++ Solution:

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode* dummy_odd = new ListNode(-1);
        ListNode* dummy_even = new ListNode(-1);
        
        ListNode* odd = dummy_odd;
        ListNode* even = dummy_even;
        
        int n = 0;
        ListNode* curr = head;
        
        while(curr != nullptr){
            n++;
            
            if(n % 2 == 1){
                odd->next = curr;
                odd = odd->next;
            }
            else{
                even->next = curr;
                even = even->next;
            }
            
            curr = curr->next;
        }
        
        even->next = nullptr;
        odd->next = dummy_even->next;
        
        return dummy_odd->next;
    }
};

Odd-Even Linked List Leetcode Java Solution:

class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode dummy_odd = new ListNode(-1);
        ListNode dummy_even = new ListNode(-1);
        
        ListNode odd = dummy_odd;
        ListNode even = dummy_even;
        
        int n = 0;
        ListNode curr = head;
        
        while(curr != null){
            n++;
            
            if(n % 2 == 1){
                odd.next = curr;
                odd = odd.next;
            }
            else{
                even.next = curr;
                even = even.next;
            }
            
            curr = curr.next;
        }
        
        even.next = null;
        odd.next = dummy_even.next;
        
        return dummy_odd.next;
    }
}

Complexity Analysis for Odd-Even Linked List Leetcode Solution

Time Complexity

The time complexity of the above code is O(N) since we traverse the entire linked list exactly once.

Space Complexity

The space complexity of the above code is O(1) since we’re using constant extra space. We had created two dummy nodes to group nodes present at odd indices followed by nodes present at even indices.