C++程序 将多级链表展开

给定一个链表，每个节点除了指向下一个节点的指针外，还有一个child指针，它可能指向一个单独的链表。这些子列表可能有一个或多个自己的子节点，以此类推，产生一个多级数据结构，如下图所示。你被给出了列表第一层的头。将列表展开，以便所有节点都出现在单层链接列表中。您需要按以下方式展开列表：一级中的所有节点应首先出现，然后是第二级的节点，依此类推。

上面的列表应转换为10->5->12->7->11->4->20->13->17->6->2->16->9->8->3->19->15

问题清楚地说明我们需要逐层展开。解决方案的想法是，我们从第一级开始，逐个处理所有节点，如果一个节点有一个子节点，那么我们将子节点附加在列表的末尾，否则，我们不做任何事情。处理完第一层后，所有下一级节点将附加在第一层之后。添加节点的过程也是同样的方式。
1) 取 “cur” 指针，它将指向列表的第一级的头
2) 取 “tail” 指针，它将指向第一层的末尾
3) 当 “curr” 不为 NULL 时，重复以下过程。
I) 如果当前节点有子节点，则
a) 将这个新的子列表附加到 “tail” 后面
tail->next = cur->child
b) 找到新子列表的最后一个节点并更新 “tail”
tmp = cur->child;
while (tmp->next != NULL)
tmp = tmp->next;
tail = tmp;
II) 移动到下一个节点，即 cur = cur->next

以下是上述算法的实现。

// 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

时间复杂度: 由于每个节点最多被访问两次，因此时间复杂度为O（n），其中n是给定链表中节点的数量。