// C++程序，用于展开有next和child指针的列表
#include <bits/stdc++.h>
using namespace std;
  
// 宏，用于找到数组中的元素数量
#define SIZE(arr) (sizeof(arr) / 
                   sizeof(arr[0])) 
  
// 链表节点有数据，next指针和child指针
class Node 
{ 
    public:
    int data; 
    Node *next; 
    Node *child; 
}; 
  
// 创建一个带n个节点的链表的实用函数，节点的数据来自arr[]，所有child指针都设置为NULL
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; 
} 
  
// 打印链表的所有节点的实用函数
void printList(Node *head) 
{ 
    while (head != NULL) 
    { 
        cout << head->data << " "; 
        head = head->next; 
    } 
    cout<<endl; 
} 
  
// 此函数创建输入列表。创建的列表与上图中所示相同
Node *createList(void) 
{ 
    int arr1[] = {10, 5, 12, 7, 11}; 
    int arr2[] = {4, 20, 13}; 
    int arr3[] = {17, 6}; 
    int arr4[] = {9, 8}; 
    int arr5[] = {19, 15}; 
    int arr6[] = {2}; 
    int arr7[] = {16}; 
    int arr8[] = {3}; 
  
    // 创建8个链接的列表
    Node *head1 = createList(arr1, 
                             SIZE(arr1)); 
    Node *head2 = createList(arr2, 
                             SIZE(arr2)); 
    Node *head3 = createList(arr3, 
                             SIZE(arr3)); 
    Node *head4 = createList(arr4, 
                             SIZE(arr4)); 
    Node *head5 = createList(arr5, 
                             SIZE(arr5)); 
    Node *head6 = createList(arr6, 
                             SIZE(arr6)); 
    Node *head7 = createList(arr7, 
                             SIZE(arr7)); 
    Node *head8 = createList(arr8, 
                             SIZE(arr8)); 
  
    /* 修改child指针以创建上面显示的列表 */
    head1->child = head2; 
    head1->next->next->next->child = head3; 
    head3->child = head4; 
    head4->child = head5; 
    head2->next->child = head6; 
    head2->next->next->child = head7; 
    head7->child = head8; 
  
  
    /* 返回第一个链接列表的头指针。请注意，head1可以访问所有节点 */
    return head1; 
} 
  
/* 展开多级链接列表的主要函数 */
void flattenList(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(); 
    flattenList(head); 
    printList(head); 
    return 0; 
} 

10 5 12 7 11 4 20 13 17 6 2 16 9 8 3 19 15