在 C++ 中反转链表
本文将演示如何在 C++ 中反转链表数据结构。
C++ 中使用迭代函数反转链表
我们假设目标对象是一个单向链表并相应地实现代码片段。首先，我们需要查看为演示示例而实现的驱动程序代码中的基本功能实用程序。
链表节点是一个简单的 struct，带有一个 string 数据对象和一个指向下一个节点的指针。我们还有 addNewNode 函数，它接受两个参数，Node* 和对 string 的引用。在 main 例程中多次调用 addNewNode 函数以构造一个新的列表对象并存储来自 data_set 向量的字符串。该函数在动态内存上分配每个节点并返回指向新创建节点的指针。
我们的链表数据结构的另一个有用函数是 printNodes，它用于将数据从每个节点输出到 cout 流。后一个将帮助我们粗略地验证反转函数的正确性。请注意，printNodes 在列表遍历期间保持节点数并打印每个元素的索引。最后，我们需要在程序退出之前释放所有节点。这一步对于反转函数演示不是必需的，但对于任何实际项目来说，清理运行时分配的所有内存都很重要。
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
string data;
};
struct Node *addNewNode(struct Node *node, string &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodes(struct Node *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct Node *tmp, *head = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
head = addNewNode(head, data_set.at(0));
tmp = head;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
}
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
输出：
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
一旦我们初始化了一个新的链表并将链表的头部存储在一个单独的指针中，我们就可以使用它来反转内容。在这种情况下，我们实现了 reverseList 函数，它接受单个 Node* 参数并返回一个新的根节点。首先，我们复制传递的指针并将其存储为 head 变量。我们还需要两个额外的 Node 类型指针在 while 循环期间进行内部簿记。
反转算法可以描述如下：我们将下一个节点指针存储在一个临时变量（next）中，并将 nullptr 值分配给原始变量。因此，原始 head 节点将指向 nullptr 作为其在列表中的下一个节点。接下来，我们更新 head 变量以存储原始列表中的下一个（第二个）节点，并将原始头节点的地址保存在一个单独的临时变量中。
我们重复前面的步骤，直到 head 指针的计算结果为 nullptr，这意味着到达列表的末尾。最后，我们返回存储在 n 临时变量中的新头节点的地址。因此，main 程序调用 printNodes 函数供用户比较修改后的链表内容。
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
string data;
};
struct Node *addNewNode(struct Node *node, string &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodes(struct Node *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
Node *reverseList(struct Node *node) {
auto head = node;
Node *n = nullptr;
Node *next = nullptr;
while (head) {
next = head->next;
head->next = n;
n = head;
head = next;
}
return n;
}
int main() {
struct Node *tmp, *head = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
head = addNewNode(head, data_set.at(0));
tmp = head;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
printNodes(reverseList(head));
freeNodes(head);
return EXIT_SUCCESS;
}
输出：
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
-----------------------------------
node 0 - data: Meteor Lake
node 1 - data: Tiger Lake
node 2 - data: Alder Lake
node 3 - data: Rocket Lake
