# 移除链表元素

题目要求：

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
输出：[]

提示：

# 方法 1

图中 s 代表 sentinel 哨兵 (如果不加哨兵，则删除第一个节点要特殊处理)，例如要删除 6

p1=s p2=1

$s \rightarrow 1 \rightarrow 2 \rightarrow 6 \rightarrow 3 \rightarrow 6 \rightarrow null$

p1=s p2=2

$s \rightarrow 1 \rightarrow 2 \rightarrow 6 \rightarrow 3 \rightarrow 6 \rightarrow null$

p1=1 p2=2

$s \rightarrow 1 \rightarrow 2 \rightarrow 6 \rightarrow 3 \rightarrow 6 \rightarrow null$

p1=2 p2=6

$s \rightarrow 1 \rightarrow 2 \rightarrow 6 \rightarrow 3 \rightarrow 6 \rightarrow null$

p1=2 p2=3

$s \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 6 \rightarrow null$

下面是完整过程图

代码：

	public ListNode removeElements(ListNode head, int val) {
	ListNode s = new ListNode(-1, head);
	ListNode p1 = s;
	ListNode p2 = s.next;
	while(p2 != null)
	{
	if(p2.val == val)
	{
	// 删除，p2 向后平移
	p1.next = p2.next;
	}else
	{
	//p1 p2 向后平移
	p1 = p1.next;
	}
	p2 = p2.next;
	}
	return s.next;
	}

思路，递归函数负责返回：从当前节点 (我) 开始，完成删除的链表

	public ListNode removeElements(ListNode p = 1, int v = 6) {
	1.next = 2
	public ListNode removeElements(ListNode p = 2, int v = 6) {
	2.next = 3
	public ListNode removeElements(ListNode p = 6, int v = 6) { // 6
	public ListNode removeElements(ListNode p = 3, int v = 6) {
	3.next = null
	public ListNode removeElements(ListNode p = 6, int v = 6) { // 6
	public ListNode removeElements(ListNode p = null, int v = 6) {
	// 没有节点，返回
	}
	}
	}
	}
	}
	}

代码：

	public ListNode removeElements(ListNode head, int val) {
	if(head == null)
	{
	return null;
	}
	if(head.val == val)
	{
	return removeElements(head.next, val);
	}else
	{
	head.next = removeElements(head.next, val);
	return head;
	}
	}