एक एकल लिंक्ड सूची इनपुट के रूप में दी गई है। लक्ष्य है सूची को दो एकल लिंक्ड सूचियों में विभाजित करना जिनमें मूल सूची के वैकल्पिक नोड्स हों। यदि इनपुट सूची में नोड्स 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 लेते हैं, एक मूल सूची के हेड को इंगित करता है और दूसरा हेड → नेक्स्ट को इंगित करता है। अब दोनों पॉइंटर्स को अगले के अगले नोड पर ले जाते हैं और उप-सूचियाँ बनाते हैं।
इंट डेटा पार्ट और Node नेक्स्ट पॉइंटर के साथ Node स्ट्रक्चर लें।
फ़ंक्शन addtohead(Node** head, int data) का उपयोग हेड पर नोड्स जोड़कर एकल लिंक्ड सूची बनाने के लिए किया जाता है।
उपरोक्त फ़ंक्शन का उपयोग करके हेड को पहले नोड के पॉइंटर के रूप में एकल लिंक्ड सूची बनाएं।
फ़ंक्शन display(Node* head) का उपयोग हेड नोड से शुरू करके लिंक्ड सूची प्रिंट करने के लिए किया जाता है।
दो Node पॉइंटर्स node1 और node2 लें।
फ़ंक्शन splitList(Node* head, Node** n1, Node** n2) नोड पॉइंटर्स लेता है और n1 को हेड और n2 को मूल सूची के हेड → नेक्स्ट पर इंगित करता है।
इसके अंदर मूल सूची को दो उप-सूचियों में विभाजित करने के लिए split(*n1, *n2) कॉल करें।
फ़ंक्शन split(Node* N1, Node* N2) N1 और N2 पॉइंटर्स लेता है और मूल सूची के वैकल्पिक नोड्स वाली दो उप-सूचियाँ बनाता है।
यदि N1 और N2 दोनों NULL हैं तो कुछ भी वापस न करें।
यदि N1->next NULL नहीं है तो tmp = N1->next->next सेट करें और N1->next = tmp।
यदि N2->next NULL नहीं है तो tmp = N2->next->next सेट करें और N2->next = tmp।
अगली पुनरावृत्ति के लिए split(N1->next, N2->next) कॉल करें।
अंत में display() का उपयोग करके उप-सूचियाँ प्रिंट करें।
उदाहरण
#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
