LeetCode 203：移除链表元素

删除链表中等于给定值 val 的所有节点。

Remove all elements from a linked list of integers that have value val.

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

两种方法，一种是迭代法，从第一个节点开始，遇到值相同的节点就将其删除。链表的删除操作是直接将删除节点的前一个节点指向删除节点的后一个节点即可。

第二种方法是递归，用递归从后向前遇到相同节点直接指向该节点的下一个节点的地址即可

由于链表删除操作的特殊性，如果要删除某个节点，必须要知道该删除节点的前一个节点地址才可完成删除操作。所以如果是从第一个节点开始判断，就要考虑到第一个节点是否为空节点、第一个节点是否就是该删除的的节点，删除头节点和非头节点的操作不一样，应单独实现删除操作。

如果原链表是这种形式：1->1->1->2 val=1 删除头节点后第二个节点置为头节点，但是第二个节点作为新的头节点依然需要删除，所以对头节点的操作应该是一个迭代过程。

另外一种方法就是新建一个虚拟节点，该虚拟节点下一个节点指向原链表头节点。这就无需考虑头节点是否为空、是否为待删除节点。如原链表为：1->1->1->2 val=1 ，新建一个虚拟节点 -1 作为头节点：-1->1->1->1->2 val=1 ，这时只需正常迭代删除即可，唯一要注意是返回节点不能是 head ，因为原链表的头节点如果是待删除节点，此时 head 节点已被删除并作为单独隔离出来的节点，并非链表内的一个节点。

Java：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
 ListNode newHead=new ListNode(-1);//新建虚拟节点
 newHead.next=head;//虚拟节点作为原链表的头节点
 ListNode cur = newHead;//遍历节点的指针

 while (cur.next != null) {
     if (cur.next.val == val) {
  cur.next = cur.next.next;//删除操作
     } else {
  cur = cur.next;
     }
 }
 return newHead.next;//返回的头节点应当是虚拟节点的下一个节点
    }
}

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
 newHead = ListNode(-1)
 newHead.next = head
 cur = newHead
 while cur.next:
     if cur.next.val == val:
  cur.next = cur.next.next
     else:
  cur = cur.next
 return newHead.next

class Solution {
    public ListNode removeElements(ListNode head, int val) {
 if (head == null) return null;//基线条件
 head.next = removeElements(head.next, val);
 if (head.val == val) {
     return head.next;
 } else {
     return head;
 }
    }
}

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
 if not head: return None
 head.next = self.removeElements(head.next, val)
 if head.val == val:
     return head.next
 else:
     return head