Odd Even Linked List - CPP Solution

1. Introduction

In this blog post, we explore an intriguing problem in linked list manipulation: reordering the nodes based on their position (odd or even). The challenge lies in maintaining the relative order within the odd and even groups and achieving this with optimal space and time complexity.

Problem

Given the head of a singly linked list, the task is to group all nodes with odd indices together followed by those with even indices. The order within each group (odd and even) must remain as it was in the input. The solution must adhere to O(1) extra space complexity and O(n) time complexity.

2. Solution Steps

1. Initialize two pointers, odd and even, to keep track of the odd and even positioned nodes.

2. Iterate through the list, alternating between moving nodes to the odd and even lists.

3. Finally, link the last node of the odd list to the head of the even list.

4. Return the head of the modified list.

3. Code Program

#include <iostream>
using namespace std;

// ListNode structure definition
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to reorder the list based on odd and even indices
ListNode* oddEvenList(ListNode* head) {
    if (!head || !head->next) return head;

    ListNode *odd = head, *even = head->next, *evenHead = even;

    while (even && even->next) {
        odd->next = odd->next->next;
        even->next = even->next->next;
        odd = odd->next;
        even = even->next;
    }

    odd->next = evenHead;
    return head;
}

// Function to print the linked list
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5
    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);

    head = oddEvenList(head);
    printList(head); // Expected output: 1 -> 3 -> 5 -> 2 -> 4 -> nullptr
    return 0;
}

Output:

1 -> 3 -> 5 -> 2 -> 4 -> nullptr

Explanation:

The oddEvenList function reorders the linked list by separating nodes into odd and even indexed nodes. It maintains two pointers, odd and even, that are used to link odd-indexed nodes and even-indexed nodes separately. 

After completing the separation, the list of odd-indexed nodes is connected to the head of the even-indexed nodes. This method ensures the list is reordered according to the specified criteria while preserving the relative order within the odd and even groups.