用 C++ 删除链表中的节点
Jinku Hu
2023年10月12日
本文将讨论如何在链表 C++ 中实现删除给定节点的函数的方法。
实现删除链表中给定节点的函数
在本文中，我们从头开始实现一个单向链表，而不使用 STL 中的容器。因此，我们需要定义一些必要的函数来管理链表中的节点。
insertNode 元素是创建新链表需要调用的核心函数。由于我们需要存储列表的头部，insertNode 返回指向 ListNode 类型节点的指针。后者是链表节点的最小表示。它只包含一个指向下一个节点的指针和 string 数据对象。
在程序的测试和演示过程中，重要的是要有一些实用函数来向用户控制台显示一些消息。在这种情况下，printNodes 元素用于打印给定列表结构中的所有节点。此外，在动态内存上分配新节点时，我们需要使用 freeNodes 函数在程序退出时释放列表中的每个现有节点。
一旦我们构建了一个包含任意数据的列表，如以下代码片段的 main 函数所示，我们就可以调用 deleteNode，它实现节点删除操作。节点的移除需要在其中处理几个极端情况。即，当给定节点与列表的头部相同时的场景，当给定节点是列表中的唯一节点时的另一个场景。
在后一种情况下，我们可以在节点指针上调用 delete 运算符并从函数返回。尽管将 nullptr 分配给地址很重要，因为这将帮助我们将新元素添加到 main 函数中的同一个 head 变量中。
另一方面，当链表中还有其他节点时，移除头节点是比较棘手的。我们必须将第二个节点的内容复制到头节点并删除前一个。请注意，每个案例都返回 EXIT_SUCCESS 值以指示成功的函数调用。
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNode(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
int deleteNode(struct ListNode *root, struct ListNode *node) {
if (node == nullptr || root == nullptr) return EXIT_FAILURE;
if (root == node) {
if (root->next == nullptr) {
delete node;
root = nullptr;
return EXIT_SUCCESS;
}
node = root->next;
root->data = root->next->data;
root->next = root->next->next;
delete node;
return EXIT_SUCCESS;
}
auto prev = root;
while (prev->next != node && prev->next != nullptr) {
prev = prev->next;
}
prev->next = node->next;
delete node;
return EXIT_SUCCESS;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
head = insertNode(head, "Xenial");
insertNode(head, "Artful");
printNodes(head);
cout << " ----------------------------------- " << endl;
deleteNode(head, head);
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
输出：
node 0 - data: Xenial
node 1 - data: Artful
-----------------------------------
node 0 - data: Artful
其余的函数代码实现了常规情况，其中给定节点从列表链中解开，然后使用 delete 运算符解除分配。但是请注意，此操作需要找到前一个节点，这是对除列表头部之外的每个节点的线性时间操作。通常，为了保证链表末尾的恒定时间移除，应该将链表的末尾存储在链表结构中。
下面的代码片段演示了一个不同的 main 函数场景，其中从列表中间删除了一个节点。
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNode(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
int deleteNode(struct ListNode *root, struct ListNode *node) {
if (node == nullptr || root == nullptr) return EXIT_FAILURE;
if (root == node) {
if (root->next == nullptr) {
delete node;
root = nullptr;
return EXIT_SUCCESS;
}
node = root->next;
root->data = root->next->data;
root->next = root->next->next;
delete node;
return EXIT_SUCCESS;
}
auto prev = root;
while (prev->next != node && prev->next != nullptr) {
prev = prev->next;
}
prev->next = node->next;
delete node;
return EXIT_SUCCESS;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
head = insertNode(head, "Xenial");
auto iter = insertNode(head, "Bionic");
insertNode(head, "Artful");
printNodes(head);
cout << " ----------------------------------- " << endl;
deleteNode(head, iter);
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
输出：
node 0 - data: Xenial
node 1 - data: Bionic
node 2 - data: Artful
-----------------------------------
node 0 - data: Xenial
node 1 - data: Artful
作者： Jinku Hu
