203. 移除链表元素

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

示例:

1
2

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

题解：

如果删除的是中间节点， 此题看起来非常简单，直接拿到prev指针，指向当前节点的next即可，但是如果删除的是头节点，就会比较麻烦，所以此题使用了虚拟头节点，初始化一个虚拟头节点，其next指针指向head。

代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

 public ListNode removeElements(ListNode head, int val) {
        // 虚拟头节点
        ListNode newHead = new ListNode(-1);

        ListNode prev = newHead;
        ListNode cur = head;

        while (cur != null){
            if (cur.val == val){
                prev.next = cur.next;
            }else {
                prev = cur;
            }
            cur = cur.next;
        }
        return newHead.next;
    }

时间复杂度 ： O（N）

空间复杂度 ： O（1）