लिंक्ड लिस्ट एक रैखिक डेटा संरचना है जिसमें प्रत्येक नोड के दो ब्लॉक होते हैं जैसे कि एक ब्लॉक में नोड का मान या डेटा होता है और दूसरा ब्लॉक अगले फील्ड का पता रखता है।
मान लीजिए हमारे पास एक लिंक्ड लिस्ट है जैसे कि प्रत्येक नोड में डेटा और एक पॉइंटर होता है जो लिंक्ड लिस्ट के अगले नोड की ओर इंगित करता है। कार्य दिए गए लिंक्ड लिस्ट को सेग्रिगेट करना है। लिंक्ड लिस्ट को सेग्रिगेट करने का अर्थ है हमें लिस्ट में विषम इंडेक्स वाले नोड्स और सम इंडेक्स वाले नोड्स को अलग करना है।
इस समस्या को हल करने का दृष्टिकोण
दिए गए लिंक्ड लिस्ट को सेग्रिगेट करने के लिए, हम विषम इंडेक्स, सम इंडेक्स, और सम इंडेक्स पर मान के लिए तीन पॉइंटर्स पेश करेंगे। उसके बाद, हम पूरे लिंक्ड लिस्ट पर पुनरावृति करेंगे और पॉइंटर को कुछ मान से इनिशियलाइज़ करेंगे।
लिंक्ड लिस्ट में, इंडेक्सिंग '1' से शुरू होती है, इस प्रकार किसी विशेष स्ट्रिंग के लिए, लिस्ट का पहला नोड हमेशा विषम इंडेक्स वाले नोड के रूप में माना जाएगा। हालांकि, अगला नोड सम इंडेक्स वाले नोड के रूप में माना जाता है।
- डेटा और अगले नोड के पॉइंटर के साथ एक लिंक्ड लिस्ट लें।
- एक फ़ंक्शन segregateList(listnode *head) हेड नोड के पॉइंटर को लेता है और आउटपुट के रूप में सेग्रिगेटेड लिंक्ड लिस्ट लौटाता है।
- तीन पॉइंटर्स oddIndex, evenIndex और evenHead इनिशियलाइज़ करें जो वर्तमान में लिस्ट के हेड की ओर इंगित कर रहे हैं।
- पूरे लिंक्ड लिस्ट पर पुनरावृति करें और oddIndex के नेक्स्ट पॉइंटर को evenIndex के नेक्स्ट पॉइंटर से इनिशियलाइज़ करें।
- अब पूरी लिस्ट पर पुनरावृति करें और evenIndex के नेक्स्ट पॉइंटर को oddIndex के नेक्स्ट पॉइंटर से इनिशियलाइज़ करें।
- हेड पॉइंटर लौटाएं।
उदाहरण
#include <iostream>
using namespace std;
class node {
public:
int data;
node * next;
node(int d) {
data = d;
next = NULL;
}
};
node * segregateList(node * head) {
if (head == NULL) {
return NULL;
}
node * oddIndex = head;
node * evenIndex = head -> next;
node * evenHead = evenIndex;
while (evenIndex != NULL and evenIndex -> next != NULL) {
oddIndex -> next = evenIndex -> next;
oddIndex = oddIndex -> next;
evenIndex -> next = oddIndex -> next;
evenIndex = evenIndex -> next;
}
oddIndex -> next = evenHead;
return head;
}
void insertAtNode(node * & head, int data) {
node * n = new node(data);
n -> next = head;
head = n;
}
void print(node * head) {
while (head != NULL) {
cout << head -> data << "->";
head = head -> next;
}
}
int main() {
node * head = NULL;
// It could be possible that the head node contains NULL Value.
insertAtNode(head, 5);
insertAtNode(head, 8);
insertAtNode(head, 3);
insertAtNode(head, 1);
insertAtNode(head, 2);
print(head);
cout << endl;
segregateList(head);
print(head);
}
उपरोक्त कोड चलाने से आउटपुट इस प्रकार उत्पन्न होगा,
आउटपुट
2->3->5->1->8->
दिया गया लिंक्ड लिस्ट है, 2->1->3->8->5->. लिंक्ड लिस्ट को सेग्रिगेट करने के बाद, यह आउटपुट के रूप में 2->3->5->1->8-> उत्पन्न करेगा।
