让我们制定问题陈述来理解删除过程。给定一个“键”，删除链表中该键的第一次出现。
迭代法：
要从链表中删除一个节点，我们需要做以下步骤。
- 找到要删除的节点的上一个节点。
- 改变上一个节点的next。
- 待删除节点的空闲内存。
由于链表的每个节点都是在 C 中使用 malloc() 动态分配的，因此我们需要调用free()来释放为要删除的节点分配的内存。
#include <bits/stdc++.h> using namespace std; class Node{ public: int data; Node* next; }; void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void deleteNode(Node** head_ref, int key) { Node* temp = *head_ref; Node* prev = NULL; if (temp != NULL && temp->data == key) { *head_ref = temp->next; delete temp; return; } else { while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } if (temp == NULL) return; prev->next = temp->next; delete temp; } } void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } int main() { Node* head = NULL; push(&head, 7); push(&head, 1); push(&head, 3); push(&head, 2); puts("Created Linked List: "); printList(head); deleteNode(&head, 1); puts("\nLinked List after Deletion of 1: "); printList(head); return 0; }
输出
Created Linked List: 2 3 1 7 Linked List after Deletion of 1: 2 3 7
递归方法：
要递归删除链表的节点，我们需要执行以下步骤。
1.我们传递node*（节点指针）作为对函数的引用（如node* &head）
2.现在由于当前节点指针是从前一个节点的下一个（通过引用传递）派生的，所以现在如果当前节点指针的值发生变化，则前一个下一个节点的值也会发生变化，这是删除节点时所需的操作（即指向前一个节点的下一个当前节点的（包含键）下一个）。
3.找到包含给定值的节点。
4.存储此节点以稍后使用 free() 函数解除分配。
5.更改此节点指针，使其指向它的下一个，并通过执行此前一个节点的下一个也得到正确链接。
下面是上述方法的实现。
#include <bits/stdc++.h> using namespace std; struct node { int info; node* link = NULL; node() {} node(int a) : info(a) { } }; void deleteNode(node*& head, int val) { if (head == NULL) { cout << "Element not present in the list\n"; return; } if (head->info == val) { node* t = head; head = head->link; delete (t); return; } deleteNode(head->link, val); } void push(node*& head, int data) { node* newNode = new node(data); newNode->link = head; head = newNode; } void print(node* head) { if (head == NULL and cout << endl) return; cout << head->info << ' '; print(head->link); } int main() { node* head = NULL; push(head, 10); push(head, 12); push(head, 14); push(head, 15); print(head); deleteNode(head, 20); print(head); deleteNode(head, 10); print(head); deleteNode(head, 14); print(head); return 0; }
输出
Element not present in the list 15 14 12 10 15 14 12 15 12
