इनपुट के रूप में सिंगल लिंक्ड लिस्ट को देखते हुए। लक्ष्य सूची को दो एकल लिंक की गई सूचियों में विभाजित करना है जिनमें मूल सूची के वैकल्पिक नोड हैं। यदि इनपुट सूची में नोड्स a → b → c → d → e → f हैं तो विभाजन के बाद, दो उप-सूचियाँ a → c → e और b → d → f होंगी।
हम दो पॉइंटर्स N1 और N2 लेंगे, एक मूल सूची के शीर्ष की ओर इशारा करता है और दूसरा शीर्ष → अगले की ओर इशारा करता है। अब दोनों पॉइंटर्स को अगले नोड के अगले नोड पर ले जाएं और सबलिस्ट बनाएं।
उदाहरण
इनपुट - सूची :- 1 → 5 → 7 → 12 → 2 → 96 → 33
आउटपुट - मूल सूची :1 5 7 12 2 96 33
सूची 1:1 7 2 33
सूची 2:5 12 96
स्पष्टीकरण - ऊपर दिखाए गए सबलिस्ट बनाने के लिए 1 और 5 से शुरू करें और अगले बिंदु से वैकल्पिक नोड्स पर जाएं।
इनपुट - सूची :- 13 → 53 → 90 → 18 → 44 → 11→ 99 → 32
आउटपुट - मूल सूची :13 53 90 18 44 11 99 32
सूची 1:13 90 44 99
सूची 2:53 18 11 32
स्पष्टीकरण - 13 और 53 से शुरू करें और ऊपर दिखाए गए सबलिस्ट बनाने के लिए वैकल्पिक नोड्स के अगले बिंदु पर जाएं।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में हम दो पॉइंटर्स N1 और N2 लेंगे, एक मूल सूची के शीर्ष की ओर इशारा करता है और दूसरा शीर्ष → अगले की ओर इशारा करता है। अब दोनों पॉइंटर्स को अगले नोड के अगले नोड पर ले जाएं और सबलिस्ट बनाएं।
-
स्ट्रक्चर नोड को इंट डेटा पार्ट और नोड को अगले पॉइंटर के रूप में लें।
-
फ़ंक्शन addtohead (नोड ** हेड, इंट डेटा) का उपयोग एकल लिंक की गई सूची बनाने के लिए सिर में नोड्स जोड़ने के लिए किया जाता है।
-
पहले नोड के सूचक के रूप में शीर्ष के साथ उपरोक्त फ़ंक्शन का उपयोग करके एक एकल लिंक की गई सूची बनाएं।
-
फ़ंक्शन डिस्प्ले (नोड * हेड) का उपयोग हेड नोड से शुरू होने वाली लिंक की गई सूची को प्रिंट करने के लिए किया जाता है।
-
दो नोड पॉइंटर्स नोड1 और नोड2 लें।
-
फ़ंक्शन स्प्लिटलिस्ट (नोड * हेड, नोड ** एन 1, नोड ** एन 2) नोड पॉइंटर्स लेता है और n1 को हेड और एन 2 को हेड → ओरिजिनल स्ट्रिंग के बगल में ले जाता है।
-
इसके अंदर स्प्लिट (*n1, *n2) को दो सबलिस्ट में मूल सूची को विभाजित करने के लिए कॉल करें
-
फ़ंक्शन स्प्लिट(नोड* N1, Node* N2) N1 और N2 पॉइंटर्स लेता है और मूल सूची के वैकल्पिक नोड्स वाले दो सबलिस्ट बनाता है।
-
अगर N1 और N2 दोनों शून्य हैं तो कुछ भी नहीं लौटाएं।
-
अगर N1→ अगला शून्य नहीं है तो tmp=N1->next->next और N1->next =tmp;
सेट करें -
f N2→ अगला शून्य नहीं है तो tmp=N2->next->next और N2->next =tmp;
सेट करें -
कॉल स्प्लिट (N1-> अगला, N2-> अगला); अगले पुनरावृत्ति के लिए।
-
अंत में डिस्प्ले () का उपयोग करके सबलिस्ट प्रिंट करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void addtohead(Node** head, int data){
Node* nodex = new Node;
nodex->data = data;
nodex->next = (*head);
(*head) = nodex;
}
void split(Node* N1, Node* N2){
Node *tmp;
if (N1 == NULL || N2 == NULL){
return;
}
if (N1->next != NULL){
tmp=N1->next->next;
N1->next = tmp;
}
if (N2->next != NULL){
tmp=N2->next->next;
N2->next = tmp;
}
split(N1->next, N2->next);
}
void splitList(Node* head, Node** n1, Node** n2){
*n1 = head;
*n2 = head->next;
split(*n1, *n2);
}
void display(Node* head){
Node* curr = head;
if (curr != NULL){
cout<<curr->data<<" ";
display(curr->next);
}
}
int main(){
Node* head = NULL;
Node *node1 = NULL, *node2 = NULL;
addtohead(&head, 20);
addtohead(&head, 12);
addtohead(&head, 15);
addtohead(&head, 8);
addtohead(&head, 10);
addtohead(&head, 4);
addtohead(&head, 5);
cout<<"Original List :"<<endl;
display(head);
splitList(head, &node1, &node2);
cout<<endl<<"List 1: ";
display(node1);
cout<<endl<<"List 2: ";
display(node2);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा
Original List : 5 4 10 8 15 12 20 List 1: 5 10 15 20 List 2: 4 8 12