双重指针删除链表节点

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;
    }
};


发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

You might also like