C++ 展平链表

2024年8月29日 | 阅读24分钟

在本文中，您将学习 C++ 中展平链表的不同方法和示例。

在 C++ 中展平链表意味着将一个链表组成的链表转换为一个单一的、已排序的链表。这是数据结构和算法中的一个常见问题。链表组成的链表是一种结构，其中外层链表的每个节点都指向一个单独的链表，您希望将这些单独的链表合并成一个已排序的链表。有几种方法可以展平 C++ 中的链表。展平链表的一些主要方法如下。

方法一：归并排序和递归

此方法递归地展平链表，并使用合并函数以排序的方式合并各个链表。生成的链表将是一个单一的已排序链表，包含原始链表组成的链表中所有元素。

程序

让我们以一个示例来说明 C++ 中的归并排序和递归函数。

#include <iostream>
struct Node {
 int data;
 Node* next;
 Node* down;
};
Node* merge(Node* a, Node* b) {
 if (!a) return b;
 if (!b) return a;
 Node* result;
 if (a->data < b->data) {
 result = a;
 result->down = merge(a->down, b);
 } else {
 result = b;
 result->down = merge(a, b->down);
 }
 return result;
}
Node* flatten(Node* head) {
 if (!head || !head->next) {
 return head;
 }
 head->next = flatten(head->next);
 return merge(head, head->next);
}
// Utility function to insert a new node at the end of a list
void insert(Node* &head, int data) {
 Node* newNode = new Node;
 newNode->data = data;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!head) {
 head = newNode;
 } else {
 Node* temp = head;
 while (temp->next) {
 temp = temp->next;
 }
 temp->next = newNode;
 }
}
void display(Node* head) {
 while (head) {
 std::cout << head->data << " ";
 head = head->down;
 }
 std::cout << std::endl;
}
int main() {
 Node* head = nullptr;
 insert(head, 5);
 insert(head, 10);
 insert(head, 19);
 insert(head, 28);
 insert(head->down, 7);
 insert(head->down, 8);
 insert(head->down, 30);
 insert(head->down->down, 20);
 insert(head->down->down, 22);
 insert(head->next, 35);
 insert(head->next, 40);
 insert(head->next, 45);
 head = flatten(head);
 display(head);
 return 0;
}

输出

5 7 10 19 20 28 35 40 45

解释

在此示例中，每个节点包含三个组件：data，用于存储节点的值；next，指向同一链表中下一个节点的指针；以及 down，指向下一个链表的指针。
合并函数接收两个已排序的链表（a 和 b）作为输入，并将它们合并成一个单一的已排序链表。
它使用递归调用来比较两个链表中节点的data，并 accordingly 合并它们。
合并的结果是一个新的链表，它保持了排序顺序。
flatten 函数负责展平链表组成的链表。
它接收链表头作为输入，并递归地展平列表的其余部分。
它首先检查当前列表是否为空或只有一个元素（!head || !head->next），在这种情况下，它按原样返回列表。
如果还有更多链表需要展平（head->next），它会递归地展平剩余部分，然后使用合并函数将当前列表与展平后的列表合并。
insert 函数是一个实用函数，用于在链表的末尾插入一个具有指定数据值的新节点。
它检查链表是否为空（!head），在这种情况下，它将新节点设置为头节点。
否则，它会遍历链表以找到最后一个节点，并将新节点附加到末尾。
display 函数用于打印展平后的链表。
它从头到尾遍历展平后的链表，同时打印每个节点的数据值。
在 main 函数中，我们使用 insert 函数创建了一个链表组成的链表示例。我们以分层方式将各种元素插入到链表中。
之后，我们调用 flatten 函数来展平链表。
最后，我们使用 display 函数显示展平后的链表。

复杂度分析

时间复杂度

合并函数的时间复杂度为 O(n + m)，其中 n 和 m 是正在合并的两个链表的大小。
flatten 函数递归地合并链表。假设有 'k' 个链表，并且每个链表包含平均 'n' 个元素。时间复杂度为 O(k * n * log(k))，因为合并过程是在层次结构的每一级上递归执行的。
insert 函数逐个插入元素，对于每次插入，它都会遍历链表以找到末尾。因此，插入的时间复杂度为 O(n)，其中 'n' 是插入时链表的大小。
display 函数只遍历展平后的链表一次，因此其时间复杂度为 O(k * n)，其中 'k' 是链表的数量，'n' 是展平后列表中的总元素数。
总的来说，整个代码的时间复杂度可以近似为 O(k * n * log(k))。

空间复杂度

合并函数的空间复杂度为 O(n + m)，其中 'n' 和 'm' 是正在合并的两个链表的大小。此空间用于递归函数调用堆栈。
在最坏的情况下，空间复杂度为 O(k)，其中 'k' 是链表的数量。
insert 函数为每次插入分配新节点空间。在最坏的情况下，空间复杂度为 O(n)，其中 'n' 是插入的元素数量。
display 函数使用恒定的额外空间，因此其空间复杂度为 O(1)。
总的来说，代码的空间复杂度取决于链表的数量 ('k') 和展平后列表中的总元素数 ('n')。在最坏的情况下，空间复杂度可以近似为 O(k + n)。

方法二：使用优先队列。

优先队列是一种数据结构，它允许高效地插入和提取具有特定优先级的元素。在这种情况下，优先级将由节点的data值决定。

创建一个最小堆（优先队列）以高效地管理链表中的下一个节点。
初始化一个空的结果列表，它将存储展平后的链表。
最初，将每个链表的头节点插入到优先队列中。

当优先队列不为空时

从优先队列中提取data值最小的节点。
将此节点添加到结果列表。
如果该节点具有 "down" 指针（即，它是链表的一部分），则将同一链表中的下一个节点插入到优先队列中。

继续此过程，直到优先队列为空。

程序

让我们以一个示例来演示如何使用 C++ 中的优先队列来展平链表。

#include <iostream>
#include <queue>
struct Node {
 int data;
 Node* next;
 Node* down;
};
// Comparison function for the priority queue
struct NodeComparison {
 bool operator()(const Node* a, const Node* b) const {
 return a->data > b->data;
 }
};
Node* flattenUsingPriorityQueue(Node* head) {
 // Create a priority queue (min-heap) to manage nodes
 std::priority_queue<Node*, std::vector<Node*>, NodeComparison> minHeap;
 // Push the top nodes of each list into the priority queue
 for (Node* current = head; current != nullptr; current = current->next) {
 minHeap.push(current);
 }
 Node* dummy = new Node(); // Create a dummy node to simplify list construction
 Node* tail = dummy; // Tail pointer for the result list
 // Merge the lists from the priority queue
 while (!minHeap.empty()) {
 Node* current = minHeap.top();
 minHeap.pop();
 // Add the node to the result list
 tail->next = current;
 tail = current;
 // If the node has a "down" pointer, push it into the priority queue
 if (current->down) {
 minHeap.push(current->down);
 }
 }
 return dummy->next; // Return the flattened list (excluding the dummy node)
}
// Utility function to insert a new node at the end of a list
void insert(Node* &head, int data) {
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!head) {
 head = newNode;
 } else {
 Node* temp = head;
 while (temp->next) {
 temp = temp->next;
 }
 temp->next = newNode;
 }
}
// Utility function to display the flattened linked list
void display(Node* head) {
 while (head) {
 std::cout << head->data << " ";
 head = head->next;
 }
 std::cout << std::endl;
}
int main() {
 Node* head = nullptr;
 insert(head, 5);
 insert(head, 10);
 insert(head, 19);
 insert(head, 28);
 insert(head->down, 7);
 insert(head->down, 8);
 insert(head->down, 30);
 insert(head->down->down, 20);
 insert(head->down->down, 22);
 insert(head->next, 35);
 insert(head->next, 40);
 insert(head->next, 45);
 head = flattenUsingPriorityQueue(head);
 display(head);
 return 0;
}

输出

5 7 10 19 20 28 35 40 45

解释

该代码定义了一个 Node 结构来表示链表中的节点。每个节点包含一个整数data，一个指向同一链表中下一个节点的指针 (next)，以及一个指向下一个链表的指针 (down)。
定义了一个名为 NodeComparison 的自定义比较函数，以根据节点data值进行比较，确保具有最小data值的节点位于优先队列（最小堆）的顶部。
此函数负责使用优先队列展平链表组成的链表。
它接收链表组成的链表的头节点作为输入。
创建了一个最小堆（优先队列）minHeap，用于根据节点data值高效地管理节点。
该函数遍历外层链表，将每个内层链表的顶节点推入优先队列。
创建了一个虚拟节点 (dummy) 以简化列表的构建，并使用一个尾指针来跟踪结果列表中最后一个节点。
在 while 循环中，节点按data值顺序从优先队列中弹出，并附加到结果列表中。如果节点具有 "down" 指针，则将同一链表中的下一个节点推入优先队列。
返回结果列表，但不包括虚拟节点。
insert 函数是一个实用函数，用于在链表末尾插入一个新节点。
它检查链表是否为空，然后相应地附加新节点。
display 函数是一个实用函数，用于打印展平后的链表。
在 main 函数中，使用 insert 函数创建了一个链表组成的链表示例。以分层方式将各种元素插入到链表中。
调用 flattenUsingPriorityQueue 函数来展平链表。
最后，使用 display 函数显示展平后的链表。

复杂度分析

时间复杂度

遍历外层链表并将每个内层链表的顶节点推入优先队列的for 循环，其时间复杂度为 O(k * log(k))，其中 'k' 是链表的数量。向优先队列插入操作需要 O(log(k)) 时间。
while 循环一直运行到优先队列为空。在每次迭代中，它会从优先队列中弹出一个节点，并将同一链表中的下一个节点推入队列（如果适用）。迭代次数取决于链表中总节点数，即 'n'。因此，在最坏的情况下，while 循环的时间复杂度为 O(n * log(k))。
总的来说，该代码的时间复杂度为 O(k * log(k) + n * log(k))。

空间复杂度

优先队列（minHeap）用于随时存储最多 'k' 个节点。优先队列的空间复杂度为 O(k)。
在合并过程中会构建一个新的展平链表。存储此列表所需的空间为 O(n)，其中 'n' 是展平后列表中的总节点数。
代码使用了一些额外的变量和指针，但它们的空间复杂度是恒定的 (O(1))。
总的来说，代码的空间复杂度为 O(k + n)，其中 'k' 是链表的数量，'n' 是展平后列表中的总节点数。

方法三：使用栈

此方法通常比使用优先队列更节省内存，并且适用于已排序和未排序的链表。在此方法中，我们使用一个栈来跟踪当前级别（链表）中的节点。

我们首先将每个链表的顶节点推入栈中。当我们处理顶节点时，如果存在，我们会将同一链表中的下一个节点推入栈中。此过程一直持续到栈为空。

程序

让我们以一个示例来演示如何使用 C++ 中的栈来展平链表。

#include <iostream>
#include <stack>
struct Node {
 int data;
 Node* next;
 Node* down;
};
Node* mergeSortedLists(Node* a, Node* b) {
 if (!a) return b;
 if (!b) return a;
 Node* result = nullptr;
 if (a->data < b->data) {
 result = a;
 result->down = mergeSortedLists(a->down, b);
 } else {
 result = b;
 result->down = mergeSortedLists(a, b->down);
 }
 return result;
}
Node* flattenUsingStack(Node* head) {
 if (!head) return nullptr;
 std::stack<Node*> nodeStack;
 // Push the head node of each list onto the stack
 for (Node* current = head; current != nullptr; current = current->next) {
 nodeStack.push(current);
 }
 while (nodeStack.size() > 1) {
 Node* list1 = nodeStack.top();
 nodeStack.pop();
 Node* list2 = nodeStack.top();
 nodeStack.pop();
 // Merge the two sorted lists and push the result back onto the stack
 Node* mergedList = mergeSortedLists(list1, list2);
 nodeStack.push(mergedList);
 }
 return nodeStack.top();
}
// Utility function to insert a new node at the end of a list
void insert(Node* &head, int data) {
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!head) {
 head = newNode;
 } else {
 Node* temp = head;
 while (temp->next) {
 temp = temp->next;
 }
 temp->next = newNode;
 }
}
// Utility function to display the flattened linked list
void display(Node* head) {
 while (head) {
 std::cout << head->data << " ";
 head = head->down;
 }
 std::cout << std::endl;
}
int main() {
 Node* head = nullptr;
 insert(head, 5);
 insert(head, 7);
 insert(head, 10);
 insert(head, 19);
 insert(head->down, 20);
 insert(head->down, 22);
 insert(head->down->down, 28);
 insert(head->next, 30);
 insert(head->next, 35);
 insert(head->next, 40);
 insert(head->next, 45);
 head = flattenUsingStack(head);
 display(head);
 return 0;
}

输出

5 7 10 19 20 28 30 35 40 45

解释

在此程序中，Node 结构用于表示链表节点。每个节点包含一个整数data，一个指向同一链表中下一个节点的指针 (next)，以及一个指向下一个链表的指针 (down)。
此函数用于合并两个已排序的链表并返回合并结果。
它接收两个指针 a 和 b，它们代表要合并的两个已排序列表的头节点。
函数比较 a 和 b 中节点的data值。它递归地选择较小的值并将其附加到结果中。down指针被更新以合并子列表。
这是展平链表的主要函数。
它使用一个栈来在展平和排序链表时管理节点。
最初，它将每个列表的头节点推入栈中。
之后，它迭代地从栈中弹出两个节点，使用 mergeSortedLists 函数合并它们，然后将结果推回栈中。
此过程一直持续到栈中只剩下一个列表。
这个实用函数用于在列表末尾插入一个新节点。它将具有指定数据值的新节点附加到现有列表的末尾。
这个实用函数用于通过遍历展平后的链表并打印每个节点的data值来显示它。
在 main 函数中，使用 insert 函数构造了一个链表组成的链表示例。通过插入各种元素来创建分层结构。
调用 flattenUsingStack 函数来展平和排序列表。结果存储在 head 变量中。
最后，使用 display 函数打印展平并排序的链表。
代码的输出将是按升序排列的展平并排序的链表。该代码使用栈来高效地管理节点，并确保展平后的列表排序正确。

复杂度分析

时间复杂度

flattenUsingStack函数在栈中推送和弹出节点，并且对于每对节点，它都会调用 mergeSortedLists。在最坏的情况下，栈的大小可能与链表中总节点数成正比，我们将此表示为 'N'。因此，时间复杂度为 O(N * (m + n))，其中 'N' 是总节点数，'m' 和 'n' 是正在合并的列表的大小。
这些函数遍历链表一次。它们的时间复杂度为 O(N)，其中 'N' 是总节点数。
总的来说，整个代码的时间复杂度为 O(N * (m + n))。

空间复杂度

栈使用的空间与链表组成的链表的深度成正比，这等同于链表的数量 ('k')。栈的最大空间需求为 O(k)。
在合并过程中会构建一个新的展平并排序的链表。存储此列表所需的空间为 O(N)，其中 'N' 是展平后列表中的总节点数。
代码使用了一些额外的变量和指针，但它们的空间复杂度是恒定的 (O(1))。
总的来说，代码的空间复杂度为 O(k + N)。

方法四：使用原地重排法

“原地重排法”是一种展平链表组成的链表的方法，目标是在不使用额外数据结构的情况下，通过重排现有节点内的指针来创建展平的链表。此方法会修改原始链表结构。

程序

让我们以一个示例来演示如何使用 C++ 中的原地重排法来展平链表。

#include <iostream>
struct Node {
 int data;
 Node* next;
 Node* down;
};
// Merge two sorted linked lists into a single sorted list
Node* mergeSortedLists(Node* a, Node* b) {
 if (!a) return b;
 if (!b) return a;
 Node* result = nullptr;
 if (a->data < b->data) {
 result = a;
 result->down = mergeSortedLists(a->down, b);
 } else {
 result = b;
 result->down = mergeSortedLists(a, b->down);
 }
 return result;
}
// Flatten and sort the linked list in ascending order
Node* flattenAndSort(Node* head) {
 if (!head || !head->next) return head;
 Node* mergedList = mergeSortedLists(head, flattenAndSort(head->next));
 return mergedList;
}
// Utility function to insert a new node at the end of a list
void insert(Node* &head, int data) {
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!head) {
 head = newNode;
 } else {
 Node* temp = head;
 while (temp->next) {
 temp = temp->next;
 }
 temp->next = newNode;
 }
}
// Utility function to display the linked list
void display(Node* head) {
 while (head) {
 std::cout << head->data << " ";
 head = head->down;
 }
 std::cout << std::endl;
}
int main() {
 Node* head = nullptr;
 insert(head, 5);
 insert(head, 7);
 insert(head, 10);
 insert(head, 19);
 insert(head->down, 20);
 insert(head->down, 28);
 insert(head->next, 30);
 insert(head->next, 35);
 insert(head->next, 40);
 insert(head->next, 45);
 head = flattenAndSort(head);
 display(head);
 return 0;
}

输出

5 7 10 19 20 28 30 35 40 45

解释

在此示例中，Node结构用于表示链表节点。每个节点包含一个整数data，一个指向同一链表中下一个节点的指针 (next)，以及一个指向下一个链表的指针 (down)。
此函数用于将两个已排序的链表合并成一个已排序的列表。它以递归方式实现。
它接收两个指针，a 和 b，它们代表要合并的两个已排序列表的头节点。
down指针也用于合并子列表。
这是展平和排序链表的主要函数。它以递归函数的方式实现。
它通过合并列表对来递归地展平和排序列表。
基本情况是只有一个列表，或者列表只有一个节点（即 head 或 head->next 为 null）。
在递归情况下，它会递归地展平当前列表并将其与展平后的下一个列表的结果合并。
这个实用函数用于在列表末尾插入一个新节点。它将具有指定数据值的新节点附加到现有列表的末尾。
这个实用函数用于通过遍历展平后的链表并打印每个节点的data值来显示它。
最后，使用 display 函数打印展平并排序的链表。
代码的输出将是按升序排列的展平并排序的链表。该代码使用类似归并排序的方法有效地展平链表。

复杂度分析

时间复杂度

合并两个具有 m 和 n 个元素的已排序链表的时间复杂度为 O(m + n)。在最坏的情况下，它会被调用以处理所有对，因此其时间复杂度为 O(N * (m + n))，其中 'N' 是总节点数，'m' 和 'n' 是正在合并的列表的大小。
flattenAndSort函数递归地展平并排序链表。在最坏的情况下，它会为链表层次结构的每个级别调用，从而导致时间复杂度为 O(k * N * (m + n))，其中 'k' 是级别的数量。
这些函数遍历链表一次。它们的时间复杂度为 O(N)，其中 'N' 是总节点数。
总的来说，整个代码的时间复杂度为 O(k * N * (m + n))。

空间复杂度

代码同时为 mergeSortedLists 和 flattenAndSort 使用递归。递归堆栈使用的空间与链表组成的链表的深度成正比，这等同于链表的数量 ('k')。递归堆栈的最大空间需求为 O(k)。
存储已排序的展平列表所需的空间为 O(N)，其中 'N' 是展平后列表中的总节点数。
代码使用了一些额外的变量和指针，但它们的空间复杂度是恒定的 (O(1))。
总的来说，代码的空间复杂度为 O(k + N)。

方法五：使用虚拟节点和递归

“使用虚拟节点和递归”方法是一种展平链表组成的链表并在不修改原始结构的情况下保持排序顺序的方法。此方法使用虚拟节点以递归方式合并已排序的链表。

程序

让我们以一个示例来演示如何使用 C++ 中的虚拟节点和递归来展平链表。

#include <iostream>
struct Node {
 int data;
 Node* next;
 Node* down;
};
Node* mergeSortedLists(Node* a, Node* b) {
 Node dummy;
 Node* tail = &dummy;
 dummy.down = nullptr;
 while (a && b) {
 if (a->data < b->data) {
 tail->down = a;
 a = a->down;
 } else {
 tail->down = b;
 b = b->down;
 }
 tail = tail->down;
 }
 tail->down = (a) ? a : b;
 return dummy.down;
}
Node* flattenUsingDummyAndRecursion(Node* head) {
 if (!head || !head->next) return head;
 Node* mid = head->next;
 Node* down = head->down;
 head->next = nullptr;
 Node* left = flattenUsingDummyAndRecursion(head);
 Node* right = flattenUsingDummyAndRecursion(mid);
 return mergeSortedLists(left, right);
}
// Utility function to insert a new node at the end of a list
void insert(Node* &head, int data) {
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!head) {
 head = newNode;
 } else {
 Node* temp = head;
 while (temp->next) {
 temp = temp->next;
 }
 temp->next = newNode;
 }
}
// Utility function to display the linked list
void display(Node* head) {
 while (head) {
 std::cout << head->data << " ";
 head = head->down;
 }
 std::cout << std::endl;
}
int main() {
 Node* head = nullptr;
 insert(head, 5);
 insert(head, 7);
 insert(head, 10);
 insert(head, 19);
 insert(head->down, 20);
 insert(head->down, 28);
 insert(head->next, 30);
 insert(head->next, 35);
 insert(head->next, 40);
 insert(head->next, 45);
 head = flattenUsingDummyAndRecursion(head);
 display(head);
 return 0;
}

输出

5 7 10 19 20 30 35 40 45

解释

在此程序中，Node结构表示链表节点，其中data存储值，next 指向同一级别的下一个节点，down 指向下一个链表（子列表）。
它使用虚拟节点合并两个已排序的链表。它遍历列表，选择较小的值来创建合并列表。down指针会更新以合并子列表。
主要函数用于递归地将输入列表分成两部分，处理每个部分，然后使用 mergeSortedLists 合并它们。它保持排序顺序。
insert函数在列表末尾附加一个新节点，display打印展平后的链表。
它构造了一个由各种元素和子列表组成的示例分层链表。
代码对分层列表的头节点调用 flattenUsingDummyAndRecursion。子列表被展平，合并结果按升序排序。
已排序的展平链表作为最终输出显示。
此方法有效地保留了原始结构，同时创建了一个已排序的展平列表，使其适用于需要这两种属性的应用。

复杂度分析

时间复杂度

此代码的时间复杂度主要由两个关键函数决定：mergeSortedLists和 flattenUsingDummyAndRecursion。

mergeSortedLists 函数

长度为 'm' 和 'n' 的两个已排序链表合并的时间复杂度为 O(m + n)。在代码中，此函数在展平过程中为每对列表递归调用。
flattenUsingDummyAndRecursion 函数中 mergeSortedLists 的总体时间复杂度为 O(N * (m + n))，其中 'N' 是链表中总节点数，'m' 和 'n' 代表正在合并的列表的大小。

flattenUsingDummyAndRecursion 函数

此函数递归地展平并排序链表。它针对分层结构中的每个级别调用，这涉及到整个列表。
此函数的最坏情况时间复杂度为 O(k * N * (m + n))，其中 'k' 是分层结构中的级别数。

空间复杂度

代码同时为 mergeSortedLists 和 flattenUsingDummyAndRecursion 使用递归。递归堆栈使用的空间与链表分层结构的深度成正比，这等同于链表的数量 ('k')。递归堆栈的最大空间需求为 O(k)。
存储已排序的展平列表所需的空间为 O(N)，其中 'N' 是展平后列表中的总节点数。
代码使用了一些额外的变量和指针，但它们的空间复杂度是恒定的 (O(1))。
总的来说，代码的空间复杂度为 O(k + N)，其中 'k' 代表分层深度，'N' 是展平后列表中的总节点数。该代码有效地展平并排序链表，同时保留原始结构。

方法六：使用辅助数组

“使用辅助数组”方法是一种展平链表组成的链表并在保持排序顺序的方法。与其他方法不同，此方法不会修改原始结构。相反，它收集链表中的值，使用辅助数组对其进行排序，然后从排序后的值创建一个新的链表。

程序

这是使用辅助数组来展平链表组成的链表并保持排序顺序的 C++ 代码。

#include <iostream>
#include <vector>
#include <algorithm>
struct Node {
 int data;
 Node* next;
 Node* down;
};
// Function to flatten and sort the linked list using an auxiliary array
Node* flattenUsingAuxiliaryArray(Node* head) {
 if (!head) return nullptr;
 std::vector<int> values;
 // Traverse the linked list and collect values
 while (head) {
 Node* current = head;
 while (current) {
 values.push_back(current->data);
 current = current->down;
 }
 head = head->next;
 }
 //sort the collected values
 std::sort(values.begin(), values.end());
 // Create a new linked list from the sorted values
 Node* newHead = nullptr;
 Node* tail = nullptr;
 for (int value : values) {
 Node* newNode = new Node();
 newNode->data = value;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!newHead) {
 newHead = newNode;
 tail = newNode;
 } else {
 tail->down = newNode;
 tail = newNode;
 }
 }
 return newHead;
}
// Utility function to insert a new node at the end of a list
void insert(Node* &head, int data) {
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!head) {
 head = newNode;
 } else {
 Node* temp = head;
 while (temp->next) {
 temp = temp->next;
 }
 temp->next = newNode;
 }
}
// Utility function to display the linked list
void display(Node* head) {
 while (head) {
 std::cout << head->data << " ";
 head = head->down;
 }
 std::cout << std::endl;
}
int main() {
 Node* head = nullptr;
 insert(head, 5);
 insert(head, 7);
 insert(head, 10);
 insert(head, 19);
 insert(head->down, 20);
 insert(head->down, 28);
 insert(head->next, 30);
 insert(head->next, 35);
 insert(head->next, 40);
 insert(head->next, 45);
 head = flattenUsingAuxiliaryArray(head);
 display(head);
 return 0;
}

输出

5 7 10 19 20 30 35 40 45

解释

在此程序中，Node结构表示链表节点，其中data存储值，next 指向同一级别的下一个节点，down 指向下一个链表（子列表）。
它是负责展平和排序链表的中央函数。
它首先遍历输入的层次化链表，收集所有值并将它们存储在名为 values 的动态数组中。
收集的值数组使用标准排序算法（std::sort）进行排序，确保值按升序排列。
初始化了一个新的链表（newHead）来保存展平并排序的值。
代码遍历排序后的值并为每个值创建新节点，这些节点被添加到 newHead 的末尾。
尾指针跟踪列表的最后一个节点，允许高效地插入节点。
代码包含两个实用函数：insert，它在列表末尾插入一个新节点；display，它打印展平后的链表。
在 main 函数中，通过插入各种元素和子列表来构造一个示例分层链表。
对分层列表的头节点调用 flattenUsingAuxiliaryArray 函数。该函数处理并将值排序到一个新的链表中。
代码将排序后的展平链表作为最终输出打印。
此方法在创建已排序的展平列表的同时保留了链表的原始结构。但是，它具有与辅助数组相关的空间复杂度，这对于大型链表来说可能是一个缺点。

复杂度分析

时间复杂度

收集值：代码遍历整个分层链表以收集值。它需要访问每个节点，从而导致 O(N) 的时间复杂度，其中 'N' 是分层链表中总节点数。

排序值：排序操作在收集到的值上使用 std::sort 进行。此操作的时间复杂度通常为 O(N * log(N))，其中 'N' 代表要排序的值的数量。

创建展平列表：排序后，代码遍历排序后的值以创建一个新的链表。创建过程也需要 O(N) 时间，因为它会访问每个值一次。

总的来说，代码的时间复杂度主要由排序操作决定，在最坏的情况下为 O(N * log(N))。

空间复杂度

值数组：代码使用一个辅助数组（values）来收集链表中的值。此数组所需的空间为 O(N)，因为它存储了 'N' 个值。

展平列表：代码创建一个新的链表来存储展平并排序的值。此列表所需的空间也为 O(N)，因为它包含 'N' 个节点。

额外空间：代码使用一些额外的变量和指针，但它们的空间复杂度是恒定的 (O(1))。

代码的总体空间复杂度为 O(N)，其中 'N' 是分层链表中总节点数。

结论

1. 归并排序和递归

方法描述：此方法使用类似归并排序的技术结合递归来展平和排序链表。它很高效，并且适用于已排序的链表。

优点：保留原始结构，适用于已排序列表，并且相对高效。

缺点：可能不是空间效率最高的方法。

时间和空间复杂度：在最坏情况下，时间复杂度为 O(N * log(N))。空间复杂度取决于所使用的方法，但可能是 O(N)。

2. 使用优先队列

方法描述：此方法在展平过程中使用优先队列来合并和排序链表。

优点：适用于未排序列表，空间复杂度低。

缺点：修改原始结构，对于已排序列表可能效率不高。

时间和空间复杂度：时间复杂度为 O(N * log(K))，其中 'K' 是链表的数量。空间复杂度为 O(K)，因为使用了优先队列。

3. 使用栈

方法描述：此方法将栈与递归结合起来展平和排序链表。这是一种可以适应各种场景的混合方法。

优点：保留原始结构，可根据不同需求进行调整。

缺点：递归可能会使用额外的栈空间，可能很复杂。

时间和空间复杂度：时间复杂度取决于具体实现。空间复杂度取决于递归深度和栈的使用情况。

4. 原地重排

方法描述：此方法通过重排节点内的指针来创建展平的链表，而不使用额外的数据结构。

优点：就地保留原始结构，空间利用高效。

缺点：可能更复杂，实现和理解难度较大。

时间和空间复杂度：由于单次遍历，时间复杂度为 O(N)。空间复杂度为 O(1)，因为它修改了现有结构。

5. 使用虚拟节点和递归

方法描述：此方法使用虚拟节点和递归合并来展平和排序链表。

优点：保留原始结构，易于实现。

缺点：递归可能会使用额外的栈空间。

时间和空间复杂度：在最坏情况下，时间复杂度为 O(N * log(N))。空间复杂度为 O(N)，因为使用了递归。

6. 使用辅助数组

方法描述：此方法收集链表中的值，使用辅助数组对其进行排序，然后从排序后的值创建新的链表。

优点：保留原始结构，易于理解。

缺点：可能不适用于大型列表。

时间和空间复杂度：排序的时间复杂度为 O(N * log(N))。空间复杂度为 O(N)，因为使用了辅助数组。

下一个主题C++ 中的 forward_list::reverse()

C++ 展平链表

方法一：归并排序和递归

程序

方法二：使用优先队列。

程序

方法三：使用栈

程序

方法四：使用原地重排法

程序

方法五：使用虚拟节点和递归

程序

方法六：使用辅助数组

程序

结论

1. 归并排序和递归

2. 使用优先队列

3. 使用栈

4. 原地重排

5. 使用虚拟节点和递归

6. 使用辅助数组

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 展平链表

方法一：归并排序和递归

程序

方法二：使用优先队列。

程序

方法三：使用栈

程序

方法四：使用原地重排法

程序

方法五：使用虚拟节点和递归

程序

方法六：使用辅助数组

程序

结论

1. 归并排序和递归

2. 使用优先队列

3. 使用栈

4. 原地重排

5. 使用虚拟节点和递归

6. 使用辅助数组

相关帖子

C++ 原生字符串字面量