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

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

}

// Function to print the linked list
cout << head->val << " -> ";
}
cout << "nullptr\n";
}

int main() {
// Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5

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.