एक सिंगल लिंक्ड लिस्ट एक रैखिक डेटा संरचना है जिसमें दो भाग होते हैं: एक डेटा और दूसरा सूची में अगले एलिमेंट का पॉइंटर।
एक वैकल्पिक विषम और सम सिंगली लिंक्ड लिस्ट एक लिंक्ड लिस्ट है जिसमें एक नोड सम डेटा वाला होता है और दूसरा नोड विषम डेटा वाला होता है।
इस समस्या में, हमें एक पूर्वनिर्धारित सिंगली लिंक्ड लिस्ट के एलिमेंट्स को दो तरीकों में से किसी एक में पुनर्व्यवस्थित करना है जो वैकल्पिक विषम और सम सिंगली लिंक्ड लिस्ट को परिभाषित करते हैं।
दो तरीके हैं: लिंक्ड लिस्ट का पहला एलिमेंट सम है तो अगला एलिमेंट विषम होना चाहिए और अगला यानी तीसरा एलिमेंट फिर से सम होना चाहिए। दूसरा प्रकार होगा यदि पहला एलिमेंट विषम है तो अगला एलिमेंट सम होना चाहिए और अगला यानी तीसरा एलिमेंट विषम होना चाहिए।
आइए एक उदाहरण देखते हैं अवधारणा को बेहतर ढंग से समझने के लिए।
मान लीजिए लिंक्ड लिस्ट है: 45 > 21 > 2 > 213 > 3 > 34 > 78 > 12।
परिणामी लिंक्ड लिस्ट होगी: 45 > 2 > 21 > 34 > 213 > 78 > 3 > 12
अब, चूंकि इस लिंक्ड लिस्ट में सम और विषम एलिमेंट्स हैं और इन्हें पुनर्व्यवस्थित करने के लिए हम 2, 34, 78, 12 को लगातार सम स्थानों पर और 45, 21, 213, 3 को लगातार विषम स्थानों पर रखेंगे।
अब, चूंकि हमने समस्या को समझ लिया है, हम इसके लिए एक समाधान खोजने की कोशिश करेंगे। इस प्रकार की समस्या को हल करने के कई तरीके हो सकते हैं। एक सरल विधि स्टैक्स का उपयोग करना होगा। हम दो स्टैक्स बनाएंगे, एक सम के लिए और एक विषम मानों के लिए। यदि हमें कोई आउट-ऑफ-ऑर्डर नोड मिलता है यानी विषम स्थान पर सम नोड, तो हम पते को सम स्टैक में पुश करेंगे और इसी तरह विषम स्टैक के लिए भी। और अंत में ट्रैवर्स करने के बाद हम स्टैक से नोड्स को पॉप करेंगे।
इस तर्क के आधार पर हम एक एल्गोरिदम बनाएंगे:
एल्गोरिदम
चरण 1: लिंक्ड लिस्ट के आउट-ऑफ-ऑर्डर सम और विषम नोड्स को रखने के लिए स्टैक्स बनाएं। चरण 2: लिंक्ड लिस्ट को ट्रैवर्स करें और अनुसरण करें: चरण 2.1: यदि विषम नोड आउट-ऑफ-ऑर्डर है यानी विषम स्थान पर, तो इसे विषम स्टैक में पुश करें। चरण 2.2: यदि सम नोड आउट-ऑफ-ऑर्डर है यानी सम स्थान पर, तो इसे सम स्टैक में पुश करें। चरण 3: स्टैक से एलिमेंट्स को वैकल्पिक क्रम में पुश करें। जब स्टैक खाली हो जाए, तो परिणाम आवश्यक लिंक्ड लिस्ट है। चरण 4: लिंक्ड लिस्ट के एलिमेंट्स प्रिंट करें।
उदाहरण
#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 << "लिंक्ड लिस्ट:" << endl; printList(head); OddEvenList(head); cout << "पुनर्व्यवस्थित करने के बाद लिंक्ड लिस्ट:" << 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(); } } आउटपुट
लिंक्ड लिस्ट: 12 78 34 3 213 2 21 45 पुनर्व्यवस्थित करने के बाद लिंक्ड लिस्ट: 3 78 45 12 213 2 21 34