इस समस्या में, हमें एक बहुस्तरीय लिंक्ड सूची दी गई है। हमारा काम एक बहुस्तरीय लिंक्ड सूची को समतल करने के लिए एक प्रोग्राम बनाना है।
फ़्लैटनिंग ऑपरेशन इस तरह से किया जाता है कि पहले स्तर के नोड्स पहले लिंक की गई सूची में होंगे और फिर दूसरे स्तर के नोड होंगे।
बहुस्तरीय लिंक की गई सूची एक बहु-आयामी डेटा संरचना है जिसमें लिंक्ड सूची के प्रत्येक नोड में दो लिंक पॉइंटर्स होते हैं, एक अगले नोड के लिए एक लिंक और एक या अधिक नोड्स वाली चाइल्ड लिस्ट के लिए एक। यह चाइल्ड पॉइंटर अन्य सूची नोड्स को इंगित कर सकता है या नहीं भी कर सकता है।
उदाहरण
समस्या को समझने के लिए एक उदाहरण लेते हैं
इनपुट
आउटपुट
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<<"The flattened Linked List is ";
while (head != NULL){
cout << head->data << " ";
head = head->next;
}
return 0;
} आउटपुट
The flattened Linked List is 1 9 8 4 6 7 3 2 5