题目

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

示例:

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

思路

1. 在链表中删除节点要将cur指针指向待删除节点的前一个节点。
   因此每次判断cur的下一个节点值是否等于val。
   但是这个逻辑不能判断链表的第一个节点，需要对第一个节点做特殊处理，具体见代码，注意这种方法有很多陷阱，有很多特殊情况做好判断。

// 不使用虚拟头结点
// 时间复杂度: O(n)
// 空间复杂度: O(1)


    public ListNode removeElements(ListNode head, int val) {

        // 需要对头结点进行特殊处理
        while(head != null && head.val == val){
            ListNode node = head;
            head = head.next;
        }

        if(head == null)
            return head;

        ListNode cur = head;
        while(cur.next != null){
            if(cur.next.val == val){
                ListNode delNode = cur.next;
                cur.next = delNode.next;
            }
            else
                cur = cur.next;
        }

        return head;
    }

2. 上面的方法因为第一个节点的特殊性，使得代码逻辑不太清晰。
   处理链表的一个重要技巧是设立虚拟头结点，初始cur指向虚拟头结点，这样就能判断到链表中的所有节点。

public ListNode removeElements(ListNode head, int val) {

        // 创建虚拟头结点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode cur = dummyHead;
        while(cur.next != null){
            if(cur.next.val == val ){
                ListNode delNode = cur.next;
                cur.next = delNode.next;
            }
            else
                cur = cur.next;
        }

        return dummyHead.next;
    }