মাল্টিলেভেল লিংকড লিস্ট ফ্ল্যাটেন করা (C++)

সমস্যা বিবরণ

একটি মাল্টিলেভেল লিংকড লিস্ট দেওয়া আছে যেখানে প্রতিটি নোডে next (সামান্য লিস্ট) এবং child (চাইল্ড লিস্ট) পয়েন্টার রয়েছে। ফ্ল্যাটেন করার সময় প্রথম লেভেলের নোডগুলো আগে থাকবে, তারপর চাইল্ড লিস্টের নোডগুলো।

উদাহরণ

ইনপুট: (চিত্র)

আউটপুট: 1 9 8 4 6 7 3 2 5

সমাধানের পদ্ধতি

লেভেল-অর্ডার ট্রাভার্সাল সদৃশ পদ্ধতি: টেইল পয়েন্টার রেখে চাইল্ড লিস্টকে মেইন লিস্টের শেষে যুক্ত করা।

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node *next, *child;
};

Node* createList(int *arr, int n) {
    Node *head=NULL, *p;
    for(int i=0;inext=new Node(); p=p->next; }
        p->data=arr[i]; p->next=p->child=NULL;
    }
    return head;
}

void flattenLinkedList(Node* head) {
    if(!head) return;
    Node *tail=head;
    while(tail->next) tail=tail->next;
    Node *cur=head;
    while(cur!=tail){
        if(cur->child){
            tail->next=cur->child;
            Node* tmp=cur->child;
            while(tmp->next) tmp=tmp->next;
            tail=tmp;
        }
        cur=cur->next;
    }
}

int main() {
    Node* head = createList();
    flattenLinkedList(head);
    cout << "Flattened List: ";
    while(head){ cout<<head->data<<" "; head=head->next; }
    return 0;
}

আউটপুট

Flattened List: 1 9 8 4 6 7 3 2 5