एक एकल लिंक की गई सूची एक रैखिक डेटा संरचना है जिसमें दो भाग होते हैं - एक डेटा और सूची में अगले तत्व के लिए अन्य पॉइंटर्स।
एक वैकल्पिक विषम और सम-एकल लिंक की गई सूची एक लिंक्ड सूची है जिसमें एक नोड सम डेटा के साथ और दूसरा नोड विषम डेटा सदस्यों के साथ होता है।
इस समस्या में, हमें एक पूर्वनिर्धारित एकल लिंक्ड सूची के तत्वों को उन दो तरीकों में से किसी एक में पुनर्व्यवस्थित करना होगा जो वैकल्पिक विषम और यहां तक कि एकल लिंक की गई सूची को परिभाषित करते हैं।
दो तरीके हैं - लिंक्ड लिस्ट का पहला एलिमेंट सम है तो अगला एलिमेंट ऑड और नेक्स्ट टू नेक्स्ट यानी तीसरा एलिमेंट इवन है। दूसरा प्रकार होगा यदि पहला तत्व विषम है तो अगला तत्व सम होना चाहिए और अगला से अगला यानी तीसरा तत्व विषम है।
आइए अवधारणा को बेहतर ढंग से समझने के लिए एक उदाहरण देखें।
मान लीजिए लिंक की गई सूची − 45> 21> 2> 213> 3> 34> 78>12 है।
परिणामी लिंक्ड सूची 45> 2>21>34> 213> 78> 3>12
. होगीअब, चूंकि इस लिंक्ड सूची में हमारे पास सम और विषम तत्व हैं और इन्हें पुनर्व्यवस्थित करने के लिए हम क्रमागत सम स्थिति में 2, 34, 78, 12 और क्रमागत विषम स्थितियों में 45, 21, 213, 3 रखेंगे।
अब, जैसा कि हम समस्या को समझ चुके हैं, हम इसका समाधान खोजने का प्रयास करेंगे। इस प्रकार की समस्या को हल करने के कई तरीके हो सकते हैं। ढेर का उपयोग करने का एक आसान तरीका होगा। हम दो स्टैक बनाएंगे, एक सम के लिए और एक विषम मानों के लिए। यदि हम किसी भी आउट ऑफ ऑर्डर नोड यानी विषम स्थिति में नोड का सामना करते हैं, तो हम पते को सम स्टैक में धकेल देंगे और इसी तरह विषम स्टैक के लिए भी। और अंत में ट्रैवर्स करने के बाद हम नोड्स को स्टैक से बाहर निकाल देंगे।
इस तर्क के आधार पर हम एक एल्गोरिथम बनाएंगे -
एल्गोरिदम
Step 1 : Create stacks for holding out of order even and odd node of the linked list. Step 2 : Traverse the linked list and follow : Step 2.1 : if odd node is out of order i.e. at odd position, push it to odd stack. Step 2.2 : If even node is out of order i.e. at even position, push it to even stack. Step 3 : Push elements from the stack in alternate order. When the stack is empty, the result is the required linked list. Step 4: Print the elements of the linked list.
उदाहरण
#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