328. Odd Even Linked List

Description

Given a singly linked list, we need to group all odd-indexed nodes together followed by the even-indexed nodes. The first node is considered odd, the second node is even, and so on. The relative order inside both the odd and even groups should remain as it was in the input. The goal is to achieve this in O(1) space complexity and O(n) time complexity.

Intuition

The problem can be visualized as rearranging the linked list into two sublists: one containing all odd-indexed nodes and the other containing all even-indexed nodes. Once we have these two sublists, we can simply concatenate the even sublist at the end of the odd sublist.

Approach

1. Initial Setup: - Check if the list is empty or has less than three nodes; if so, return the head as it is. - Initialize two pointers: odd pointing to the first node and even pointing to the second node. Keep a reference to the head of the even sublist (evenHead), as we'll need to append it at the end.
2. Reordering: - Traverse the list, where the odd pointer skips to the next odd node and the even pointer skips to the next even node. - If the next odd node exists, update the odd pointer to point to it, otherwise stop. - If the next even node exists, update the even pointer to point to it, otherwise stop.
3. Concatenation: - Once the traversal is complete, link the last odd node to the head of the even sublist. - Set the last node of the even sublist to None to terminate the list.
4. Return: - Return the modified head of the list.

Complexity

Time Complexity:

O(n), where n is the number of nodes in the linked list. The list is traversed only once.

Space Complexity:

O(1), since we are rearranging the nodes in place and not using any extra space other than a few pointers.

Code

C++

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next || !head->next->next)
            return head;
        
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even;
        bool oddIncrement = true, evenIncrement = true;
        
        while (odd && even && (oddIncrement || evenIncrement)) {
            if (odd->next && odd->next->next) {
                odd->next = odd->next->next;
                odd = odd->next;
            } else {
                oddIncrement = false;
            }
            
            if (even->next && even->next->next) {
                even->next = even->next->next;
                even = even->next;
            } else {
                evenIncrement = false;
            }
        }
        
        odd->next = evenHead;
        even->next = nullptr;
        
        return head;
    }
};

Python

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head or not head.next or not head.next.next:
            return head
        
        odd = head
        even = head.next
        even_head = even
        odd_increment = True
        even_increment = True
        
        while odd and even and (odd_increment or even_increment):
            if odd.next and odd.next.next:
                odd.next = odd.next.next
                odd = odd.next
            else:
                odd_increment = False
            
            if even.next and even.next.next:
                even.next = even.next.next
                even = even.next
            else:
                even_increment = False
        
        odd.next = even_head
        even.next = None
        
        return head

Java

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null)
            return head;
        
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        boolean oddIncrement = true, evenIncrement = true;
        
        while (odd != null && even != null && (oddIncrement || evenIncrement)) {
            if (odd.next != null && odd.next.next != null) {
                odd.next = odd.next.next;
                odd = odd.next;
            } else {
                oddIncrement = false;
            }
            
            if (even.next != null && even.next.next != null) {
                even.next = even.next.next;
                even = even.next;
            } else {
                evenIncrement = false;
            }
        }
        
        odd.next = evenHead;
        even.next = null;
        
        return head;
    }
}

JavaScript

var oddEvenList = function(head) {
    if (!head || !head.next || !head.next.next)
        return head;
    let odd = head, even = head.next, evenHead = even, oddIncrement = true, evenIncrement = true;
    while (odd && even && (oddIncrement || evenIncrement)) {

        if (odd.next && odd.next.next) {
            odd.next = odd.next.next;
            odd = odd.next;

        } else
            oddIncrement = false;

        if (even.next && even.next.next) {
            even.next = even.next.next;
            even = even.next;
            
        } else
            evenIncrement = false;
    }
    odd.next = evenHead;
    even.next = null;
    
    return head;
};