链表中删除一个节点的方法
时间: 2023-04-06 07:03:37 浏览: 114
可以使用双指针法,先找到要删除节点的前一个节点,然后将前一个节点的 next 指针指向要删除节点的下一个节点即可。代码实现如下:
```
void deleteNode(ListNode* node) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != node) {
prev = curr;
curr = curr->next;
}
if (prev) {
prev->next = curr->next;
} else {
head = curr->next;
}
delete curr;
}
```
相关问题
链表中删除一个节点的方法有哪些
链表中删除一个节点的方法有以下几种:
1. 直接删除节点:将要删除节点的前一个节点的指针指向要删除节点的后一个节点,然后释放要删除节点的内存空间。
2. 标记删除节点:在要删除节点的数据结构中添加一个标记,表示该节点已被删除,但是不释放内存空间,可以在后续操作中再次利用该内存空间。
3. 双指针法:使用两个指针,一个指向要删除节点的前一个节点,另一个指向要删除节点的后一个节点,然后将前一个节点的指针指向后一个节点,最后释放要删除节点的内存空间。
4. 递归删除:使用递归的方式删除节点,先递归到要删除节点的前一个节点,然后将要删除节点的指针指向后一个节点,最后释放要删除节点的内存空间。
双向链表删除最后一个节点
双向链表删除最后一个节点的操作如下:
1. 判断链表是否为空,如果为空则无法进行删除操作,直接返回。
2. 判断链表是否只有一个节点,如果是则将头节点和尾节点都指向NULL,释放最后一个节点的内存,然后返回。
3. 如果链表不止一个节点,那么先找到尾节点的前一个节点,即倒数第二个节点,可以通过循环遍历或者直接使用尾节点的prev指针来找到。
4. 将倒数第二个节点的next指针指向NULL,然后释放尾节点的内存即可。
下面是C++代码实现:
```c++
struct ListNode {
int val;
ListNode *prev;
ListNode *next;
ListNode(int x) : val(x), prev(NULL), next(NULL) {}
};
void deleteLastNode(ListNode* &head, ListNode* &tail) {
if (head == NULL) {
return;
}
if (head == tail) {
delete head;
head = NULL;
tail = NULL;
return;
}
ListNode *p = tail->prev;
p->next = NULL;
delete tail;
tail = p;
return;
}
```