C++ এ এককভাবে লিঙ্কযুক্ত তালিকায় বিকল্প বিজোড় এবং জোড় নোড

একটি একক লিঙ্কযুক্ত তালিকা হল একটি রৈখিক ডেটা স্ট্রাকচার যাতে দুটি অংশ থাকে - একটি ডেটা এবং তালিকার পরবর্তী উপাদানের জন্য অন্য পয়েন্টার৷

একটি বিকল্প বিজোড় এবং এককভাবে লিঙ্কযুক্ত তালিকা একটি লিঙ্ক করা তালিকা যার একটি নোড জোড় ডেটা এবং অন্য নোড বিজোড় ডেটা সদস্য রয়েছে৷

এই সমস্যায়, আমাদের একটি পূর্বনির্ধারিত এককভাবে লিঙ্কযুক্ত তালিকার উপাদানগুলিকে দুটি উপায়ে পুনর্বিন্যাস করতে হবে যা বিকল্প বিজোড় এবং এককভাবে লিঙ্কযুক্ত তালিকাকে সংজ্ঞায়িত করে৷

দুটি উপায় হল - লিঙ্কযুক্ত তালিকার প্রথম উপাদানটি এমনকি তারপরের উপাদানটি বিজোড় হওয়া উচিত এবং পরেরটির পরেরটি অর্থাৎ তৃতীয় উপাদানটি আবার জোড়। অন্য প্রকার হবে যদি প্রথম উপাদানটি বিজোড় হয় তাহলে পরবর্তী উপাদানটি জোড় এবং পরেরটির পরেরটি অর্থাৎ তৃতীয় উপাদানটি বিজোড় হওয়া উচিত।

ধারণাটি আরও ভালভাবে বোঝার জন্য আসুন একটি উদাহরণ দেখি।

ধরুন লিঙ্ক করা তালিকা হল − 45> 21> 2> 213> 3> 34> 78> 12৷

ফলস্বরূপ লিঙ্কযুক্ত তালিকাটি হবে 45> 2>21>34> 213> 78> 3>12

এখন, যেহেতু এই লিঙ্কযুক্ত তালিকায় আমাদের জোড় এবং বিজোড় উপাদান রয়েছে এবং এইগুলিকে পুনর্বিন্যাস করতে আমরা 2, 34, 78,12 পরপর জোড় অবস্থানে এবং 45, 21, 213, 3 পরপর বিজোড় অবস্থানে রাখব।

এখন, যেহেতু আমরা সমস্যাটি বুঝতে পেরেছি আমরা এর সমাধান খুঁজে বের করার চেষ্টা করব। এই ধরনের সমস্যা সমাধানের একাধিক উপায় থাকতে পারে। একটি সহজ পদ্ধতি স্ট্যাক ব্যবহার করা হবে. আমরা দুটি স্ট্যাক তৈরি করব, একটি জোড়ের জন্য এবং একটি বিজোড় মানের জন্য। আমরা যদি কোনো ক্রমবর্ধমান নোডের সম্মুখীন হই, যেমন জোড় নোড বিজোড় অবস্থানে, আমরা ঠিকানাটিকে জোড় স্ট্যাকের দিকে ঠেলে দেব এবং একইভাবে বিজোড় স্ট্যাকের জন্যও। এবং শেষে ট্র্যাভার্স করার পরে আমরা স্ট্যাকের বাইরে নোডগুলি পপ করব।

এই যুক্তির উপর ভিত্তি করে আমরা একটি অ্যালগরিদম −

অ্যালগরিদম

উদাহরণ

#include নেমস্পেস ব্যবহার করে std;struct Node { int data; struct Node* next;};void printList(struct Node* node); Node* newNode(int key){ Node* temp =new Node; temp->ডেটা =কী; temp->পরবর্তী =NULL; return temp;}Node* insertBeg(Node* head, int val){ Node* temp =newNode(val); 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 <<"লিঙ্ক করা তালিকা:" <data <<" "; নোড =নোড->পরবর্তী; } cout < odd; স্ট্যাক<নোড*> এমনকি; 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->পরের; i++; } যখন (!odd.empty() &&!even.empty()) { swap(odd.top()->data, even.top()->data); odd.pop(); even.pop(); }}

আউটপুট

লিঙ্ক করা তালিকা:12 78 34 3 213 2 21 45 পুনর্বিন্যাস করার পরে লিঙ্ক করা তালিকা:3 78 45 12 213 2 21 34