Odd Even Linked List medium

Problem Statement

Given the head of 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 first node is considered odd, the second node is even, and so on.

Note:

• The relative order inside both the even and odd groups should remain as it was in the input.
• You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Example 1

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

Example 2

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

Steps

1. Handle edge cases: If the list is empty or has only one node, return the head.

2. Initialize pointers: Create pointers odd and even to track the heads of the odd and even sublists, respectively. Also, create pointers odd_tail and even_tail to track the tails of the odd and even sublists for efficient appending.

3. Iterate through the list: Iterate through the linked list, using a current pointer.

4. Separate odd and even nodes: For each node:

   • If the node's index is odd, append it to the odd sublist using odd_tail.
   • If the node's index is even, append it to the even sublist using even_tail.

5. Connect odd and even sublists: After iterating, connect the tail of the odd sublist to the head of the even sublist.

Explanation

The algorithm maintains two separate lists – one for odd-indexed nodes and one for even-indexed nodes. It iterates through the original list, assigning each node to its respective list. Finally, it links the tail of the odd list to the head of the even list to produce the reordered list. This approach ensures that the relative order within each group (odd and even) is preserved. The use of tail pointers avoids the need to traverse the lists repeatedly for appending nodes, contributing to the O(n) time complexity.

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) return head; // Handle edge cases

        ListNode* odd = head;          // Head of odd sublist
        ListNode* even = head->next;    // Head of even sublist
        ListNode* odd_tail = odd;       // Tail of odd sublist
        ListNode* even_tail = even;     // Tail of even sublist
        ListNode* current = even->next; // Current node for iteration

        bool odd_turn = false; //true for odd false for even. starts with even

        while (current) {
            if(odd_turn){
                odd_tail->next = current;
                odd_tail = odd_tail->next;
            } else {
                even_tail->next = current;
                even_tail = even_tail->next;
            }
            current = current->next;
            odd_turn = !odd_turn;
        }
        
        odd_tail->next = even;
        even_tail->next = nullptr;

        return odd;
    }
};

Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list. We iterate through the list once.
• Space Complexity: O(1). We use only a constant number of pointers.