সিংলি লিংকড লিস্ট একটি লিনিয়ার ডেটা স্ট্রাকচার যেতে দুটি অংশ থাকে - একটা ডেটা আরেকটা পরবর্তী উপাদানের পয়েন্টার।
অল্টারনেট ওড-ইভেন সিংলি লিংকড লিস্ট হলো এমন লিংকড লিস্ট যেটিতে একটি নোডে ইভেন ডেটা এবং পরবর্তী নোডে ওড ডেটা থাকে।
এই সমস্যায় আমাদের একটি पूर्वনির্ধারিত সিংলি লিংকড লিস্টের উপাদানগুলোকে দুটি পদ্ধতিতে যেকোনো একটি অনুযায়ী সাজাতে হবে যা অল্টারনেট ওড-ইভেন লিংকড লিস্ট ডিফাইন করে।
দুটি পদ্ধতি: প্রথম উপাদান ইভেন হলে পরবর্তীটার ওড হবে এবং তারপর আবার ইভেন। অন্য পদ্ধতিতে প্রথম উপাদান ওড হলে পরবর্তীটি ইভেন এবং তারপর আবার ওড।
উদাহরণ দিয়ে বুঝি। ধরা যাক লিংকড লিস্টটি: 45 > 21 > 2 > 213 > 3 > 34 > 78 > 12।
ফলাফল লিংকড লিস্ট হবে: 45 > 2 > 21 > 34 > 213 > 78 > 3 > 12
এই লিংকড লিস্টে ইভেন ও ওড উপাদান আছে। সাজাতে হলে ২, ৩৪, ৭৮, ১২ কনsekutিভ ইভেন পজিশনে এবং ৪৫, ২১, ২১৩, ৩ কনsekutিভ ওড পজিশনে রাখতে হবে।
এখন সমাধান খুঁজি। এই ধরণের সমস্যা সমাধানের একাধিক পদ্ধতি আছে। একটি সহজ পদ্ধতি স্ট্যাক ব্যবহার। দুটি স্ট্যাক বানাব - একটা ইভেনের জন্য, একটা ওডের জন্য। যদি আউট অফ অর্ডার নোড পাওয়া যায় (অর্থাৎ ওড পজিশনে ইভেন নোড), তবে ইভেন স্টকে পুশ করুন এবং একইভাবে ওড স্টকে। ট্রাভার্সাল শেষে স্ট্যাক থেকে পপ করে সাজান।
এই লজিকের ভিত্তিতে অ্যালগরিদম:
আলগরিদম
Step 1: আউট অফ অর্ডার ইভেন ও ওড নোড রাখার জন্য স্ট্যাক বানান।
Step 2: লিংকড লিস্ট traverser করুন এবং ফলো করুন:
Step 2.1: যদি ওড নোড আউট অফ অর্ডার হয় (ওড পজিশনে), ওড স্টকে পুশ করুন।
Step 2.2: যদি ইভেন নোড আউট অফ অর্ডার হয় (ইভেন পজিশনে), ইভেন স্টকে পুশ করুন।
Step 3: স্ট্যাক থেকে উপাদানগুলো অল্টারনেট অর্ডারে পপ করুন। স্ট্যাক খালি হলে রেজাল্ট প্রাপ্ত লিংকড লিস্ট।
Step 4: লিংকড লিস্টের উপাদান প্রিন্ট করুন।
C++ প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void printList(struct Node* node) ;
Node* newNode(int key){
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
Node* insertBeg(Node* head, int val){
Node* temp = newNode(val);
temp->next = head;
head = temp;
return head;
}
void OddEvenList(Node* head) ;
int main(){
Node* head = newNode(45);
head = insertBeg(head, 21);
head = insertBeg(head, 2);
head = insertBeg(head, 213);
head = insertBeg(head, 3);
head = insertBeg(head, 34);
head = insertBeg(head, 78);
head = insertBeg(head, 12);
cout << "Linked List:" << endl;
printList(head);
OddEvenList(head);
cout << "Linked List after " << "Rearranging:" << endl;
printList(head);
return 0;
}
void printList(struct Node* node){
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
void OddEvenList(Node* head){
stack<Node*> odd;
stack<Node*> even;
int i = 1;
while (head != nullptr) {
if (head->data % 2 != 0 && i % 2 == 0) {
odd.push(head);
}
else if (head->data % 2 == 0 && i % 2 != 0) {
even.push(head);
}
head = head->next;
i++;
}
while (!odd.empty() && !even.empty()) {
swap(odd.top()->data, even.top()->data);
odd.pop();
even.pop();
}
}
আউটপুট
Linked List: 12 78 34 3 213 2 21 45 Linked List after Rearranging: 3 78 45 12 213 2 21 34
