cpp
Node* del_node(Node* head, int val){
Node** pp=&head;
for(; *pp ; ){
Node* p=*pp;
if(p->val == val){
*pp = p->next;
delete p;
}else
pp = &p->next;
}
return head;
}
代码解析:
首先,双重指针没那么可怕,平常心。现在来讲讲这段代码干了什么。
首先,我们获取到了head指针的地址,此时,pp是指向head的指针。
然后,逐个检查元素值,如果节点不是我们要删除的节点,就跳到下个节点,即 pp = &p->next。
如果遇到了要删除的节点,即 p->val == val,我们更新 *pp 的值为 p->next,这个操作将p的值更新为了 p->next,那么前节点的next指针就指向了当前节点的下一个节点,然后使用 delete p 执行节点删除。
可能就有人问了,我先建立一个指针 Node* cur = head,然后使用cur = cur->next的方法依次遍历,若cur->val == val,再 Node* temp = cur; cur = cur->next; delete temp; 不就行了?
答案是不行的,因为此时 cur 是一个单独指向当前节点的指针,并不会改变 cur 指向的节点的指针的位置。
为了获取链表中指针的真实存放位置,我们需要在开头就使用 &head 获取指针的内存地址,这样才能获取到链表节点的真实位置。
大概讲明白了,来道力扣题吧:
https://leetcode.cn/problems/remove-nth-node-from-end-of-list
可能会有人这么写:
cpp
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* fastPtr = head, *slowPtr = head;
while(n--) {
fastPtr = fastPtr->next;
}
while(fastPtr != nullptr) {
fastPtr = fastPtr->next;
slowPtr = slowPtr->next;
}
// 此时 slowPtr 指向要被删除的节点
ListNode** pp = &slowPtr;
cout << slowPtr->val << endl;
*pp = slowPtr->next;
delete slowPtr;
return head;
}
};
这就犯了上面提到的错误。现在给出正确解法:
cpp
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode** fastPtr = &head, **slowPtr = &head;
while(n--) {
fastPtr = &((*fastPtr)->next);
}
while(*fastPtr != nullptr) {
fastPtr = &((*fastPtr)->next);
slowPtr = &((*slowPtr)->next);
}
ListNode* pp = *slowPtr;
*slowPtr = pp->next;
delete pp;
return head;
}
};
发表回复