203. 移除链表元素

题目链接
代码随想录

分析

如果要移除的节点是头节点，其操作跟要移除的节点是非头节点的时候不一样，很容易就想到，我们可以加一个虚拟头节点，然后统一移除操作。最后返回的时候，只返回虚拟节点的下一个节点即可，代码写出来非常优雅。
此外我们要想清楚，链表如何移除一个节点，自己是无法删除自己的，要删除自己，只能让自己的前一个节点的 next 指针指向自己的 next 节点，这样就删除了自己，但是我们没有指向父节点的指针，因此我们只能在遍历到自己的父节点的时候删除自己，换个角度，就是我们得在当前节点判断子节点要不要删除，因此，思路就出来了。
这里还有一个需要注意的地方，就是，如果下一个节点就是要删除的节点假设是 A1，删除之后，新的下一个节点是 A2，此时，我们还得继续检查 A2，因为 A2 可能也是要删除的节点。也就是说此时不要移动当前指针指向的节点。而如果下一个节点不是，那么就可以移动当前指针指向的节点。这么说有点绕，但是看代码就很清楚
假设输入规模为 n，算法复杂度为 $O(n)$

解题

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode nowNode = dummyHead;
        while(nowNode.next!=null){
            if(nowNode.next.val == val ){
                // nowNode 不变，下一轮循环继续检查新的 nowNode.next.next
                nowNode.next = nowNode.next.next;
            }else{
                // nowNode 更新
                nowNode =  nowNode.next;
            }
        }
        return dummyHead.next;
    }
}

相关题