Problem Statement

Given a singly linked list, rearrange the linked list such that all nodes positioned at odd indices are grouped together followed by nodes at even indices. You should maintain the relative order of the nodes within each group (odd and even).

Examples

Example 1:

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

Example 2:

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

Approaches

1️⃣ Reordering

Approach:

The idea is to use two pointers to traverse the list: one (odd) that connects all nodes at odd indices and another (even) that connects all nodes at even indices.

Here’s a step-by-step approach to solving this problem:

1. Initialization:
   • Check if the list is empty or has only one node. In these cases, no rearrangement is needed.
   • Initialize two pointers: odd for the head of the odd-index nodes and even for the head of the even-index nodes.
   • Keep a pointer evenHead to remember the start of the even nodes list, as you will need it later to connect the end of the odd nodes list to the start of the even nodes list.
2. Traverse the List:
   • While traversing, link all odd nodes together by making odd->next point to odd->next->next.
   • Similarly, link all even nodes together by making even->next point to even->next->next.
   • Move both odd and even pointers to the next node in their respective sequences.
3. Connect Odd and Even Lists:
   • After the traversal, connect the last odd node to the head of the even nodes list (evenHead).
4. Return the Head:
   • The head of the modified list remains the same as the original head.

Edge Cases:

• Return the head itself if the list is empty or has only a single element.

Code:

#include <iostream>

// Define the Node structure
struct ListNode {
    int data;
    ListNode* next;

    // Constructor to initialize the node with data
    ListNode(int value) : data(value), next(nullptr) {}
};

// Function to rearrange the linked list into odd and even nodes
ListNode* oddEvenList(ListNode* head) {
    if (!head || !head->next) return head; // Return if list is empty or has only one node

    ListNode* odd = head;           // Pointer to the first odd node
    ListNode* even = head->next;    // Pointer to the first even node
    ListNode* evenHead = even;      // Keep the start of even nodes to connect later

    while (even && even->next) {
        odd->next = even->next;     // Link odd nodes
        odd = odd->next;            // Move to next odd node
        even->next = odd->next;     // Link even nodes
        even = even->next;          // Move to next even node
    }

    odd->next = evenHead; // Connect the end of odd list to the start of even list
    return head;
}

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head) {
        std::cout << head->data << " -> ";
        head = head->next;
    }
    std::cout << "nullptr" << std::endl;
}

// Main function to test the odd-even linked list function
int main() {
    // Create a linked list 1 -> 2 -> 3 -> 4 -> 5 -> nullptr
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    std::cout << "Original list: ";
    printList(head);

    // Rearrange the list to group odd and even nodes
    head = oddEvenList(head);

    std::cout << "Rearranged list (odd and even nodes): ";
    printList(head);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
  • The solution requires only one pass through the list to rearrange the nodes, making the time complexity linear with respect to the number of nodes in the list (n).
• Space Complexity: O(1)
  • The solution does not use any additional space for data storage; it rearranges the nodes in place, so the space complexity is constant.