एक लिंक्ड सूची एक रैखिक डेटा संरचना है जिसमें प्रत्येक नोड में दो ब्लॉक होते हैं जैसे कि एक ब्लॉक में नोड का मान या डेटा होता है और दूसरे ब्लॉक में अगले फ़ील्ड का पता होता है।
आइए मान लें कि हमारे पास एक लिंक्ड लिस्ट है जैसे कि प्रत्येक नोड में डेटा और एक पॉइंटर होता है जो लिंक्ड लिस्ट के अगले नोड की ओर इशारा करता है। कार्य दी गई लिंक्ड सूची को अलग करना है। लिंक की गई सूची को अलग करने का मतलब है कि हमें सूची में विषम अनुक्रमित नोड्स और यहां तक कि इंडेक्स नोड्स को अलग करना होगा।
इस समस्या को हल करने का तरीका
किसी दी गई लिंक्ड सूची को अलग करने के लिए, हम क्रमशः विषम सूचकांक, सम सूचकांक और सम सूचकांक पर मान के लिए तीन पॉइंटर्स पेश करेंगे। उसके बाद, हम पूरी लिंक की गई सूची पर पुनरावृति करेंगे और कुछ मान के साथ पॉइंटर को इनिशियलाइज़ करेंगे।
लिंक की गई सूची में, अनुक्रमण '1' से शुरू होता है, इस प्रकार किसी विशेष स्ट्रिंग के लिए, सूची के पहले नोड को हमेशा एक विषम अनुक्रमित नोड के रूप में माना जाएगा। हालांकि, अगले नोड को एक समान अनुक्रमित नोड के रूप में माना जाता है।
- डेटा और पॉइंटर के साथ लिंक की गई सूची को अगले नोड पर ले जाएं।
- एक फ़ंक्शन segregateList(listnode *head) पॉइंटर को हेड नोड पर ले जाता है और आउटपुट के रूप में अलग की गई लिंक्ड सूची को लौटाता है।
- तीन पॉइंटर्स ऑडइंडेक्स, इवनइंडेक्स और इवनहेड को इनिशियलाइज़ करें जो वर्तमान में सूची के शीर्ष की ओर इशारा कर रहे हैं।
- संपूर्ण लिंक्ड सूची पर पुनरावृति करें और ऑडइंडेक्स के अगले पॉइंटर को समइंडेक्स के अगले पॉइंटर के साथ इनिशियलाइज़ करें।
- अब पूरी सूची पर पुनरावृति करें और सम इंडेक्स के अगले पॉइंटर को ऑडइंडेक्स के अगले पॉइंटर से इनिशियलाइज़ करें।
- हेड पॉइंटर लौटाएं।
उदाहरण
#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-> के रूप में आउटपुट देगा।