算法力扣刷题记录六【203移除链表元素】

前言

链表篇，开始。
记录六：力扣【203移除链表元素】

一、数据结构——链表

来源【代码随想录】，总结：
（1）线性结构。内存地址不连续，通过指针指向串联一起。
（2）链表类型：

单链表
- 单一方向。一个指针，指后继元素即可。
双向链表
- 两个方向。一个节点内两个指针，一个指前，一个指后。
循环链表
- 链表首尾相连。最后一个节点的指针不是null，而是指向头结点。可以用来解决约瑟夫环问题。

（3）链表定义（用C++）

//定义节点
struct Listnode{
	int data;//数据，int可以换别的，看要放什么data
	int* p;//指针，单链表就一个
	//int* pred;指前面的指针
	//int* succ;指后面的指针
};

C++中struct和class类似，同样可以用成员函数，都是自定义类型。
可以typedef另起一个名字。比如：

typedef struct Listnode{
	int data;//数据，int可以换别的，看要放什么data
	Listnode* pred;//指前面的指针
	Listnode* succ;//指后面的指针
}Node;
Node n1;
n1.data = 5;

（4）链表操作
总结：操作指针。

删除元素记得用一个临时指针指向被删掉的元素，自己释放掉，不然指针一改，就找不到被删的那个元素，但还在内存中占地。
添加元素，改指针指向。
添加/删除，都是O(1)，就一个元素。但前提得先查找到位置。
所以查找（遍历）过程是O(n)。

二、题目阅读和理解

题目阅读

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
在这里插入图片描述

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

二、第一次尝试

思路

（1）先看下对于单链表节点的定义。
（2）从头结点循环往下找节点，遇到=val删掉改变指针。

虽然知道链表删除都是操作指针但实现时需要注意方法。

实现成功

先上代码，通过测试：

/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* removed_pred = nullptr;
        ListNode* removed = nullptr;
        ListNode* search = nullptr ;//遍历指针

        if(head){
            while(head->val == val){
                removed = head;
                if(!(head->next)){
                    head = nullptr;
                    delete removed;
                    return head;
                }
                head = head->next;
                //search = search->next;
                delete removed;
            }
            removed_pred = head;
            search = head -> next;
            while(search !=nullptr){   
                if(search->val == val ){
                    removed = search;
                    search = search->next;
                    removed_pred->next = search;
                    delete removed;
                }else{
                    removed_pred = search;
                    search = search->next; 
                }
                 
            }
            return head;
        }else{
            return head;
        }
    }
};

解释过程

（1）需要返回头结点：

当头结点=val时，head需要一直后移；当头结点不等于val时，head不需要再移动，只用看后面的节点谁等于val，被删去，所以这里需要一个指针来查找后面元素，此时head固定不再移动。

所以先实现头结点=val，head一直后移：
while(head->val == val){  //当head不等于val时，不再循环，开始往后查找，head也就固定不动。
        removed = head;	//由于考虑到删除节点所在内存，所以用removed指针先指向被删除的节点，等链表指针改动完成后，delete。
        head = head->next;  //头指针需要后移；（有缺陷）
        search = search->next; //search是查找指针，初始化为head；
        delete removed;	//把“应该删去的节点”内存释放掉
    }



再实现当head固定时，查找节点并删除操作：
while(search -> next){   				//search指向正在被判断的节点，看它要不要删去；当操作到最后一个节点时，无法进入循环，所以后面要特别处理。
        if(search->val == val ){		//判断当前节点等于val
            removed = search;			//removed含义，方便释放节点内存
            search = search->next;	    //search移到下一位
            removed_pred->next = search;	//跨过待删除的节点，指向下一位。
            delete removed;
        }
        //判断当前节点不等于val
        removed_pred = search;		    // removed_pred指向待删除节点的前一位，需要记下来，改变  removed_pred的指向。
        search = search->next;
    }
    if(search -> val == val){           //处理最后一个节点
        removed_pred->next = nullptr;
    }
    return head;	//返回链表

（2）注意“-> next”很容易赋值到nullptr（空指针），导致访问空指针的运行错误。

所以还要考虑以下可能：

head指向空，初始传入参数head == nullptr;所以修正一：

在最外层加if(head)，如果不为空，开始while操作head；else 直接返回head；
链表只有一个节点，且该节点 = val。所以修正二：

//这两行很容易赋值到nullptr，紧跟着后面while(search -> next)导致访问空指针运行错误。
head = head->next; //头指针需要后移；（有缺陷）
search = search->next;
用例[1,2,1]，val=2。进入while（search -> next）后，走到if条件符合进入if逻辑，此时removed_pred=nullptr，又一次操作了空指针。所以修正三。

修正结束：

//通过测试
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* removed_pred = nullptr;
        ListNode* removed = nullptr;
        ListNode* search = nullptr ;//遍历指针

        if(head){
            while(head->val == val){
                removed = head;
                if(!(head->next)){
                    head = nullptr;
                    delete removed;
                    return head;
                }
                head = head->next;
                //search = search->next;
                delete removed;
            }
            removed_pred = head;
            search = head -> next;
            while(search !=nullptr){   
                if(search->val == val ){
                    removed = search;
                    search = search->next;
                    removed_pred->next = search;
                    delete removed;
                }else{
                    removed_pred = search;
                    search = search->next; 
                }
                 
            }
            return head;
        }else{
            return head;
        }
    }
};

最终得到提交版本。

代码随想录

学习内容

（1）解法一：移除头节点和中间节点分开操作。

//发现即使分开操作的思想，我写的也很复杂。重新实现(有错)，一写就废
/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {

        while((head != nullptr)&&(head->val == val)){
            head=head->next;
            ListNode* tmp = head;	//这里出错，先tmp再head=head->next。
            delete tmp;
        }

        ListNode* cur = head;    
        //while(cur->next != nullptr )//同时判断cur != nullptr
        while(cur->next != nullptr && cur != nullptr){	//有错
            if(cur->next->val == val){
                ListNode* tmp = cur->next;
                cur -> next=cur->next->next;
                delete tmp;
            }else{
                cur = cur->next;
            }
        }

        return head;
    }
};

注意：

先把要删除的节点给tmp后，再移动指针。
while((cur != nullptr)&&(cur->next != nullptr) ) //先判断cur再判断cur->next

（2）解法：虚拟头节点：统一节点删除操作。

//根据dummy node思想尝试写一遍
/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy_node = new ListNode(0,head);
        ListNode* search = dummy_node;
        while(search->next != nullptr){
            if(search ->next-> val ==val){
                ListNode* removed = search->next;       
                search->next = search->next->next;
                delete removed;
            }else{			//必须要有else
                search = search->next;
            }
            
        }
        delete dummy_node;	//dummy_node也要释放。
        return dummy_node->next;
    }
};

总结

（1）判断指针空不空，while(search != nullptr)。while(search)是错的。
（2）加一个虚拟头节点，可以统一删除和添加操作。不用区分删除/添加时：头节点还是中间节点。

（欢迎指正，转载标明出处）

最后有个问题，希望能得到解决

我写出下面的逻辑，但是运行时力扣报错：我非法访问，但我找不到地方。显示说search=head处。请问该怎么解决，欢迎留言。

Line 74: Char 28:
=================================================================
==20==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000098 at pc 0x5599d37f919c bp 0x7ffd3cb611f0 sp 0x7ffd3cb611e8

/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* removed_pred = nullptr;
        //ListNode* removed = nullptr;
        ListNode* search = nullptr ;//遍历指针

        while(head != nullptr){
            if(head->val == val){
                ListNode* removed = head;
                head = head->next;
                delete removed;
            }else{
                break;  //当head不在等于val，head固定。进入查找删除。
            }
        }

        search = head;

        while((search != nullptr) && (search->next != nullptr)  ){
            removed_pred = search;
            if(search->val == val ){
                ListNode* removed = search;
                search = search->next;
                removed_pred->next = search;    //如果没有(search->next != nullptr)，这里操作空指针。
                delete removed;
            }else{
                search = search->next; 
            }
        } 
        return head;
    }
};

自我回答：

找到问题了：
在if(search->val == val )这里判断的是search，而不是search->next->val。

所以改完之后，也就是学习内容中的解法一：

//测试通过
/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {


        ListNode* search = nullptr ;//遍历指针

        while(head){
            if(head->val == val){
                ListNode* removed = head;
                head = head->next;
                delete removed;
            }else{
                break;  //当head不在等于val，head固定。进入查找删除。
            }
        }

        search = head;

        while(search != nullptr && search->next != nullptr){
            if(search->next->val == val ){
                ListNode* removed = search->next;
                search->next = search->next->next;
                delete removed;
            }else{
                search = search->next; 
            }
        }
        return head;
    }
};