203.移除链表元素：
给你一个链表的头节点 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 <= 500 <= val <= 50
思考：
本题是一道经典的对链表这种数据结构的考察，主要考察了对链表中元素删除的操作。删除某个节点，其实只需要将上个节点指向该结点的下个结点即可。在c语言中需要将被删除的结点进行释放操作。
需要特别注意的是，删除头指针的方式和非头指针的方式是有所不同的，因为头指针的前面是没有上一个节点的。
保留头指针：
将头结点和其他节点分开来讨论，写出两种不同的删除方式。
/**
* 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) {
//delete head;
while (head != NULL && head->val==val)
{
ListNode* tmp = head;
head = head->next;
delete tmp;
}
//delete other nodes;
ListNode* cur=head;//将cur指向头指针开始遍历
while(cur!=NULL && cur->next!=NULL)
{
if (cur->next->val == val) { //实际操作删除修改的是cur->next即cur后一个元素
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
return head;
}
};
虚拟头结点：
我们还可以通过创建虚拟头结点的方式，在原来的头结点前再另加一个新头结点，原来的头结点就变成了第二个结点，这样的话，对于所有的结点都可以使用同一种删除方式。
/**
* 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* newHead = new ListNode(0);//设置虚拟头结点
newHead->next = head;//原来的头结点称为第二位
ListNode* cur = newHead;//剩下的操作只需考虑一种删除
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 = newHead->next;//还原头结点
delete newHead;
return head;
}
};
往期回顾：
LeetCode54. 螺旋矩阵
LeetCode59.螺旋矩阵II
LeetCode977.有序数组的平方
LeetCode844.比较含退格的字符串
LeetCode283.移动零
LeetCode27.移除元素
LeetCode26.删除有序数组中的重复项
LeetCode209.长度最小的子数组
LeetCode904. 水果成篮
LeetCode242.有效的字母异位词
LeetCode76.最小覆盖子串
