数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++ 中的多级链表扁平化
在这个问题中，我们给定一个多级链表。我们的任务是创建一个程序来扁平化这个多级链表。
扁平化操作以这样的方式进行：第一级节点将首先出现在链表中，然后是第二级节点。
**多级链表**是一种多维数据结构，其中链表的每个节点都有两个链接指针，一个指向下一个节点的链接，另一个指向具有一个或多个节点的子列表。此子指针可能指向或可能不指向其他列表节点。
示例
让我们来看一个例子来理解这个问题
输入
输出
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
更新于：2022年1月31日
449 次浏览
广告