链表删除
Harshit Jindal
2023年1月30日
2021年3月21日
在本文中,我们将学习如何从链表中删除节点。
链表删除算法
令 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 <bits/stdc++.h>
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)
。
Author: Harshit Jindal
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn