লিঙ্কড লিস্ট সেগ্রিগেশন মানে অড ইনডেক্সের নোডগুলো একসাথে এবং ইভেন ইনডেক্সের নোডগুলো একসাথে আনা (ইনডেক্স ১-ভিত্তিক)। উদাহরণ: 1→2→3→4→5 → 1→3→5→2→4
অ্যালগরিদম
- তিনটি পয়েন্টার: oddHead, evenHead, evenStart।
- ট্রাভার্সালের সময় odd-র next = even-র next, even-র next = odd-র next।
- শেষে odd-র next = evenStart।
- টাইম কমপ্লেক্সিটি: O(n), স্পেস: O(1)
উদাহরণ কোড
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* segregateList(Node* head) {
if (!head) return nullptr;
Node *odd = head, *even = head->next, *evenHead = even;
while (even && even->next) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}
void print(Node* head) {
while (head) {
cout << head->data << "->";
head = head->next;
}
cout << endl;
}
int main() {
Node* head = nullptr;
// 2→1→3→8→5 (ইনসার্ট অ্যাট হেড করলে উল্টো হয়)
for (int x : {5, 8, 3, 1, 2}) {
Node* n = new Node(x);
n->next = head;
head = n;
}
cout << "Original: "; print(head);
head = segregateList(head);
cout << "Segregated: "; print(head);
return 0;
}
আউটপুট
Original: 2->1->3->8->5-> Segregated: 2->3->5->1->8->
