链表删除算法
链接列表删除图解
链接列表删除实施
链表删除算法的复杂性
在本文中，我们将学习如何从链表中删除节点。
链表删除算法
令 head 为指向链表第一个节点的指针，令 temp 为要从链表中删除的节点的值。
迭代算法
初始化指针 curr 指向 head 以遍历链接列表，而将 prev 设置为 NULL 以在删除时跟踪 temp 之前的节点。
如果要删除的节点是 head 即 temp！=NULL && curr->data==temp，则将 head 设置为 curr->next 并删除 curr。
否则，请执行以下操作，直到我们到达要删除的节点为止。
prev=temp。
temp=temp->next。
如果 temp==NULL，返回；
将 prev->next 设置为 temp->next，并删除 temp 节点。
递归算法
如果 head==NULL，则链表为空，没有要删除的元素。因此，返回；
如果 head->data==temp，即我们找到了要删除的节点
将 head 存储在临时节点 t 中。
将 head 设置为 head->next 以删除该节点。
删除 t 并返回到较早的递归调用。
如果以上条件均不满足，则递归调用 head->next 上的 deleteNode() 以继续寻找节点。
链接列表删除图解
假设我们具有以下链接列表 1 -> 2 -> 3 -> 4，并且我们想删除值为 3 的节点。
用值 1 和 prev 将指向 head 节点的指针 curr 初始化为 NULL。
反复移动 curr，直到到达值为 3 和 prev 为 2 的节点。
将 prev（即 2）指向 curr->next（即 4）。
删除值为 3 的 curr 节点。
链接列表删除实施
#include
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
this->data = x;
this->next = NULL;
}
};
void deleteNode(Node*& head, int val) {
if (head == NULL) {
cout << "Element not present in the list\n";
return;
}
if (head->data == val) {
Node* t = head;
head = head->next;
delete (t);
return;
}
deleteNode(head->next, val);
}
void deleteiter(Node** head, int x) {
Node* temp = *head;
Node* prev = NULL;
if (temp != NULL && temp->data == x) {
*head = temp->next;
delete temp;
return;
} else {
while (temp != NULL && temp->data != x) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
delete temp;
}
}
void printList(Node* head) {
Node* curr = head;
while (curr != NULL) {
cout << curr->data << " ";
curr = curr->next;
}
cout << "\n";
}
int main() {
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
printList(head);
deleteNode(head, 3);
printList(head);
deleteiter(&head, 4);
printList(head);
return 0;
}
链表删除算法的复杂性
时间复杂度
平均情况
要删除链接列表中第 i 个位置的节点，我们必须访问 i 个节点。因此，时间复杂度约为 O(i)。而且，链表中有 n 个节点，因此平均情况下的时间复杂度为 O(n/2) 或 O(n)。时间复杂度约为 O(n)。
最佳情况
最好的情况是当我们要删除链接列表的开头时。最佳情况下的时间复杂度是 O(1)。
最坏情况
最坏情况下的时间复杂度是 O(n)。这与平均情况下的时间复杂度相同。
空间复杂度
在迭代实现的情况下，此算法的空间复杂度为 O(1)，因为它除了临时变量外不需要任何数据结构。
在递归实现中，由于递归调用堆栈所需的空间，空间复杂度为 O(n)。
Enjoying our tutorials? Subscribe to DelftStack on YouTube to support us in creating more high-quality video guides. Subscribe