इस समस्या में, हमें एक मल्टीलेवल लिंक्ड सूची दी गई है। हमारा कार्य मल्टीलेवल लिंक्ड सूची को समतल करने के लिए एक प्रोग्राम बनाना है।
समतल करने का ऑपरेशन इस तरह से किया जाता है कि पहले स्तर के नोड्स पहले लिंक्ड सूची में आएंगे और फिर दूसरे स्तर के नोड्स आएंगे।
मल्टीलेवल लिंक्ड सूची एक बहुआयामी डेटा संरचना है जिसमें लिंक्ड सूची का प्रत्येक नोड दो लिंक पॉइंटर्स रखता है, एक अगले नोड का लिंक और एक चाइल्ड सूची का लिंक जिसमें एक या अधिक नोड्स होते हैं। यह चाइल्ड पॉइंटर अन्य सूची नोड्स को इंगित कर भी सकता है और नहीं भी।
उदाहरण
समस्या को समझने के लिए एक उदाहरण लेते हैं
इनपुट
आउटपुट
1-> 9-> 8 -> 4 -> 6-> 7-> 2-> 3-> 5
समाधान दृष्टिकोण
समस्या का एक सरल समाधान लेवल ऑर्डर ट्रैवर्सल प्रकार के एल्गोरिदम का उपयोग करके करना है। हम पहले नोड से शुरू करके लिंक्ड सूची को पार करेंगे और उसी स्तर के सभी नोड्स को पार करेंगे। यदि किसी नोड के लिए कोई चाइल्ड पॉइंटर मौजूद है, तो टेल पॉइंटर का उपयोग करके इसे वर्तमान लिंक्ड सूची के अंत में ले जाएं। फिर लिंक्ड सूची के प्रत्येक चाइल्ड नोड के लिए समान ट्रैवर्सल को पुनरावर्ती रूप से करें। नीचे दिया गया प्रोग्राम तर्क को बेहतर ढंग से विस्तृत करेगा।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <bits/stdc++.h> using namespace std; #define SIZE(arr) (sizeof(arr)/sizeof(arr[0])) class Node{ public: int data; Node *next; Node *child; }; Node *createList(int *arr, int n){ Node *head = NULL; Node *p; int i; for (i = 0; i < n; ++i){ if (head == NULL) head = p = new Node(); else{ p->next = new Node(); p = p->next; } p->data = arr[i]; p->next = p->child = NULL; } return head; } Node *createList(void){ int arr1[] = {1, 9, 8, 4, 6}; int arr2[] = {7, 3, 2}; int arr3[] = {5}; Node *head1 = createList(arr1, (sizeof(arr1)/sizeof(arr1[0]))); Node *head2 = createList(arr2, (sizeof(arr2)/sizeof(arr2[0]))); Node *head3 = createList(arr3, (sizeof(arr3)/sizeof(arr3[0]))); head1->child = head2; head1->next->child = head3; return head1; } void flattenLinkedList(Node *head){ if (head == NULL) return; Node *tmp; Node *tail = head; while (tail->next != NULL) tail = tail->next; Node *cur = head; while (cur != tail){ if (cur->child){ tail->next = cur->child; tmp = cur->child; while (tmp->next) tmp = tmp->next; tail = tmp; } cur = cur->next; } } int main(void){ Node *head = NULL; head = createList(); flattenLinkedList(head); cout<<"समतल लिंक्ड सूची है "; while (head != NULL){ cout << head->data << " "; head = head->next; } return 0; } आउटपुट
समतल लिंक्ड सूची है 1 9 8 4 6 7 3 2 5
