এই সমস্যায়, আমরা একটি মাল্টিলেভেল লিঙ্ক তালিকা দেওয়া হয়. আমাদের কাজ হল একটি মাল্টিলেভেল লিঙ্কড লিস্ট সমতল করার জন্য প্রোগ্রাম তৈরি করা।
ফ্ল্যাটেনিং অপারেশনটি এমনভাবে করা হয় যে প্রথম স্তরের নোডগুলি প্রথমে লিঙ্কযুক্ত তালিকায় উপস্থিত হবে এবং তারপরে দ্বিতীয় স্তরের নোডগুলি ঘটবে৷
মাল্টিলেভেল লিঙ্কড তালিকা একটি বহুমাত্রিক ডেটা স্ট্রাকচার যাতে লিঙ্ক করা তালিকার প্রতিটি নোডে দুটি লিঙ্ক পয়েন্টার থাকে, একটি পরবর্তী নোডের লিঙ্ক এবং একটি বা একাধিক নোড সহ চাইল্ড লিস্টে। এই চাইল্ড পয়েন্টার অন্য তালিকা নোড নির্দেশ করতে পারে বা নাও পারে৷
৷উদাহরণ
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক
ইনপুট
আউটপুট
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
