Làm phẳng danh sách liên kết đa cấp (Multilevel Linked List) trong C++

Cho danh sách liên kết đa cấp (multilevel linked list) - mỗi nút có con trỏ next (cùng cấp) và child (cấp con). Nhiệm vụ: làm phẳng danh sách sao cho các nút cấp 1 đứng trước, sau đó cấp 2...

Ví dụ minh họa

Input: Danh sách đa cấp (hình ảnh)

Output: 1 9 8 4 6 7 3 2 5

Phương pháp giải

Duyệt theo thứ tự cấp độ (level order). Duyệt tất cả nút cùng cấp, nếu có child thì nối vào cuối danh sách hiện tại bằng con trỏ tail. Đệ quy xử lý các nút con.

Ví dụ chương trình

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

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

Node *createList(int *arr, int n){
    Node *head = NULL, *p = NULL;
    for (int i = 0; i < n; ++i){
        if (!head) 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, 5);
    Node *head2 = createList(arr2, 3);
    Node *head3 = createList(arr3, 1);
    head1->child = head2;
    head1->next->child = head3;
    return head1;
}

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 << "Danh sách liên kết đã làm phẳng: ";
    while (head){
        cout << head->data << " ";
        head = head->next;
    }
    return 0;
}

Kết quả

Danh sách liên kết đã làm phẳng: 1 9 8 4 6 7 3 2 5