《题目难度：简单》
（1）题目描述
给你一个链表的头节点
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
输出：[ ]
LeetCode链接：203. 移除链表元素
（2）解题思路
1）思路1：找到等于 val 的节点直接删除
定义一个指针 cur，用来遍历链表，找到等于 val 的节点
定义一个指针 prev，保存 cur 的上一个节点的位置
定义一个指针 next，保存 cur 的下一个节点的位置，用来迭代
首先判断 cur 指向节点的值是否等于 val：
如果等于，则要删除这个节点。我们需要将 prev->next 指向 next 指针，然后 free(cur)，再将 cur 往前移动到 next 指针的位置，这样就完成对这个节点的删除啦
- 如果不等于，只需要将 prev 指针和 cur 指针往前移动一位即可，继续遍历链表寻找等于 val 的节点
- 最后返回头节点指针 head 即可
- 需要考虑这一点
如果要删除的节点是头节点，所以在删除的时候需要额外判断一下是不是头结点。
- 代码如下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val){
//解题思路：遍历链表，找到满足Node.val == val的节点
struct ListNode* cur = head;
struct ListNode* prev = head; //保存cur的上一个节点位置
while(cur != NULL) //遍历链表
{
if(cur->val == val) //找到等于val的节点
{
struct ListNode* next = cur->next; //保存cur的下一个节点位置
if(head == cur) //判断cur是否是头节点
{
head = next;
}
else
{
prev->next = next; //将cur上一个节点和cur下一个节点相连
}
free(cur); //删除等于val的节点
cur = next;
}
else if(cur->val != val)
{
prev = cur;
cur = prev->next;
}
}
return head;
}
2）思路2：将不等于 val 的节点尾插到一个新链表中
- 把链表中所有不等于 val 的节点尾插到一个新链表中，相当于删除了等于val的节点
- 定义一个指针 cur，用来遍历原链表，找到不等于 val 的节点
- 定义一个指针 newhead，指向新链表的头节点
- 定义一个指针 tail，保存新链表尾节点的位置
首先判断 cur 指向节点的值是否不等于 val：
如果不等于，则需要将其尾插到新链表中，首次尾插时，新链表为空，我们让 newhead 指向 cur，然后让 tail 指向 cur，更新新链表的尾节点，cur 往后移动一位，指向待遍历的下一个节点，最后将尾节点的 next 指针置空。
- 如果等于，则要删除这个节点。定义一个指针 next 保存 cur 的下一个节点的位置，然后 free(cur)，再将 cur 移动到 next 的位置，继续遍历原链表。
- 最后返回新链表的头节点指针 newhead 即可
- 代码如下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val){
//解题思路：把链表中所有不等于val的节点尾插到一个新链表中，相当于删除了等于val的节点
struct ListNode* newhead = NULL; //新链表初始为空
struct ListNode* tail = newhead; //记录新链表尾节点的位置
struct ListNode* cur = head;
while(cur != NULL)
{
if(cur->val != val) //把链表中所有不等于val的节点尾插到一个新链表中
{
if(newhead == NULL) //新链表为空时
{
newhead = cur;
}
else //新链表不为空时
{
tail->next = cur;
}
tail = cur; //更新尾节点
cur = cur->next; //cur指向原链表中的下一个节点
tail->next = NULL; //将尾节点置空
}
else if(cur->val == val)
{
struct ListNode* next = cur->next; //保存cur的下一个节点位置
free(cur); //删除等于val的节点
cur = next;
}
}
return newhead;
}
大家快去动手练习一下吧！