lc[链表]---203.移除链表元素

一、题目描述

数据结构类型声明：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

 本人ac代码(当做无头链表来处理--->分成是否是头结点分别去处理即可。)

class Solution 
{
public:
    ListNode* removeElements(ListNode* head, int val) 
    {
        ListNode* pre=head;
        ListNode *pMove=head;
        while(pMove!=nullptr)
        {
            if(pMove==head&&pMove->val==val)
            {//要删除的是头结点
                ListNode *tmp=head;
                head=head->next;
                delete tmp;
                tmp=nullptr;
                pre=head;//++
                pMove=head;
                continue;
            }
            else if(pMove->val==val)
            {
                ListNode*tmp=pMove;
                pre->next=pMove->next;
                pMove=pMove->next;
                delete tmp;
                tmp=nullptr;
                continue;
            }
            pre=pMove;//++
            pMove=pMove->next;
        }
        return head;
    }
};

再做此题的时候，遇到了"heap use after free address"问题:

class Solution 
{
public:
    ListNode* removeElements(ListNode* head, int val) 
    {
        ListNode* pre=head;
        ListNode *pMove=head;
        while(pMove!=nullptr)
        {
            if(pMove==head&&pMove->val==val)
            {//要删除的是头结点
                ListNode *tmp=head;
                head=head->next;
                delete tmp;
                tmp=nullptr;
            }
            else if(pMove->val==val)
            {
                ListNode*tmp=pMove;
                pre->next=pMove->next;
                delete tmp;
                tmp=nullptr;
            }
            pre=pMove;//++
            pMove=pMove->next;
        }
        return head;
    }
};

问题大概出现在,比如当年你删除掉头结点的时候,pre和pMove还是指在原来那个被删除的结点上面,所以导致这样的问题(注意删除相应节点之后,要及时对pre和pMove更新即可.)--->修正代码见上。

二、其他写法-----有头链表(统一对删除结点的操作)

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};