203. 移除链表元素 - 力扣（LeetCode）

题目描述

给你一个链表的头节点 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

---

解题

数据结构里早就学过怎么删除链表元素了，原本以为可以手拿把掐，没想到一写就出各种细节上的问题！！

这道题唯一的难点就是在于怎么处理返回这个头结点，题目中的这个头结点是带有数据的，而不是指向第一个有效结点的结点 ，所以是有可能为待删除元素的，而删除这个头结点和删除其他节点的操作有所不同。

 解法一：使用原来的链表来进行移除节点操作

/*** 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*p;if(head==NULL)return NULL;//处理头结点为待删结点的情况while(head != nullptr&&head->val==val){ //注意这个条件判断的前后顺序p=head;head=head->next;delete p;  //c/c++要记得释放内存}p=head; while(p&&p->next){ //要这两个都不为空才行if(p->next->val==val){ListNode*q=p->next;p->next=p->next->next;delete q;}else{p=p->next; //这里不是每次都要执行的}}return head;}
};

有几个点特别容易错..

1.while(head != nullptr&&head->val==val) 两个判断的前后顺序千万不能反..一定要先判断是否为空，再判断是否等于val. 因为当head为空时先判断head->val==val会造成访问空指针的错误！

2.使用c/c++要记得释放内存！

3.while(p&&p->next) 两个条件都要满足 因为后面的删除操作会访问p->next；

4.p=p->next不是每次循环都要执行的，只有不删除元素时才执行，如果删除了元素就不执行（可以画个图进行理解）

---

解法二：引入虚拟头结点

 如果我们引入一个虚拟的头结点，那删除头结点和其他结点的操作就统一了。

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode*dummy=new ListNode(0),*q;dummy->next=head;q=dummy;while(q&&q->next){if(q->next->val==val){ListNode*p=q->next;q->next=q->next->next;delete p;}else{q=q->next;}}return dummy->next;}
};

这里有一个易错点就是要记得为虚拟头结点申请空间