# LeetCode 203、移除链表元素
# 一、题目描述
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
# 二、题目解析
移除的节点有两种情况。
1、移除的是头节点
2、移除的是其它节点
对于移除其它节点这种情况，我们可以让它的前一个节点指向移除节点的下一节点来解决。
对于移除头节点这种情况，为了让解决情况和上面的逻辑一样，我们借助一个虚拟节点来解决。
我们给链表添加一个虚拟头节点作为新的头节点。
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 移除链表元素（ LeetCode 203 ）:https://leetcode-cn.com/problems/remove-linked-list-elements/
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 边界情况，如果链表为空，那么没有元素可以删除，直接返回空
if (head == null) return null;
// 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
// 设置虚拟节点的目的是为了让原链表中所有节点就都可以按照统一的方式进行移除
// 因为如果不设置虚拟节点，如果删除的元素是原链表中的头节点，那么需要额外的做一些判断，比较繁琐
ListNode dummy = new ListNode(-1);
// 虚拟头节点的下一节点指向 head 节点
// 如果原链表是 1 --> 2 --> 3
// 那么加上虚拟头节点就是 -1 --> 1 --> 2 --> 3
dummy.next = head;
// 设置一个指针，指向此时的虚拟节点
// pre: -1 --> 1 --> 2 --> 3
ListNode pre = dummy;
// 设置一个指针，指向原链表 head
ListNode cur = head;
// 让 cur 不断的向后移动，直到移动到链表的最尾部，指向 null 的那个位置
// 此时 pre 还在指向 dummy
// 也就是说一开始 pre 落后 cur 一个节点
while (cur != null) {
// 移动的过程中，如果发现当前的节点值和目标值一样
// 我们就让指针 pre 所指向的节点的下一节点跳过这个值
if (cur.val == val) {
// 让指针 pre 所指向的节点的下一节点跳过这个值
pre.next = cur.next;
} else {
// 否则的话，pre 跟上 cur 的位置
pre = cur;
}
// 判断完当前的节点情况后，让 cur 向后移动
cur = cur.next;
}
// 最后返回 dummy 节点的下一节点
// 因为这个时候 dummy 指向的是一个我们设置的节点，它的下一节点才是原链表中的节点
return dummy.next;
}
}
# **2、**C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 移除链表元素（ LeetCode 203 ）:https://leetcode-cn.com/problems/remove-linked-list-elements/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 边界情况，如果链表为空，那么没有元素可以删除，直接返回空
if(head == NULL) return NULL;
// 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
// 设置虚拟节点的目的是为了让原链表中所有节点就都可以按照统一的方式进行移除
// 因为如果不设置虚拟节点，如果删除的元素是原链表中的头节点，那么需要额外的做一些判断，比较繁琐
ListNode *dummy = new ListNode(-1);
// 虚拟头节点的下一节点指向 head 节点
// 如果原链表是 1 --> 2 --> 3
// 那么加上虚拟头节点就是 -1 --> 1 --> 2 --> 3
dummy->next = head;
// 设置一个指针，指向此时的虚拟节点
// pre: -1 --> 1 --> 2 --> 3
ListNode *pre = dummy;
// 设置一个指针，指向原链表 head
ListNode *cur = head;
// 让 cur 不断的向后移动，直到移动到链表的最尾部，指向 NULL 的那个位置
// 此时 pre 还在指向 dummy
// 也就是说一开始 pre 落后 cur 一个节点
while ( cur != NULL ) {
// 移动的过程中，如果发现当前的节点值和目标值一样
// 我们就让指针 pre 所指向的节点的下一节点跳过这个值
if (cur->val == val) {
// 让指针 pre 所指向的节点的下一节点跳过这个值
pre->next = cur->next;
} else {
// 否则的话，pre 跟上 cur 的位置
pre = cur;
}
// 判断完当前的节点情况后，让 cur 向后移动
cur = cur->next;
}
// 最后返回 dummy 节点的下一节点
// 因为这个时候 dummy 指向的是一个我们设置的节点，它的下一节点才是原链表中的节点
return dummy->next;
}
};
# 3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 移除链表元素（ LeetCode 203 ）:https://leetcode-cn.com/problems/remove-linked-list-elements/
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
# 边界情况，如果链表为空，那么没有元素可以删除，直接返回空
if head == None :
return None
# 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
# 设置虚拟节点的目的是为了让原链表中所有节点就都可以按照统一的方式进行移除
# 因为如果不设置虚拟节点，如果删除的元素是原链表中的头节点，那么需要额外的做一些判断，比较繁琐
dummy = ListNode(-1)
# 虚拟头节点的下一节点指向 head 节点
# 如果原链表是 1 --> 2 --> 3
# 那么加上虚拟头节点就是 -1 --> 1 --> 2 --> 3
dummy.next = head
# 设置一个指针，指向此时的虚拟节点
# pre: -1 --> 1 --> 2 --> 3
pre = dummy
# 设置一个指针，指向原链表 head
cur = head
# 让 cur 不断的向后移动，直到移动到链表的最尾部，指向 None 的那个位置
# 此时 pre 还在指向 dummy
# 也就是说一开始 pre 落后 cur 一个节点
while cur != None :
# 移动的过程中，如果发现当前的节点值和目标值一样
# 我们就让指针 pre 所指向的节点的下一节点跳过这个值
if cur.val == val :
# 让指针 pre 所指向的节点的下一节点跳过这个值
pre.next = cur.next
else :
# 否则的话，pre 跟上 cur 的位置
pre = cur
# 判断完当前的节点情况后，让 cur 向后移动
cur = cur.next
# 最后返回 dummy 节点的下一节点
# 因为这个时候 dummy 指向的是一个我们设置的节点，它的下一节点才是原链表中的节点
return dummy.next
# 四、复杂度分析
时间复杂度：O(n)，其中 nn 是链表的长度。需要遍历链表一次。
空间复杂度：O(1)。