卷进大厂系列之LeetCode刷题笔记：移除链表元素（简单）

卷进大厂系列之LeetCode刷题笔记：移除链表元素（简单） 学算法，刷力扣，加油卷，进大厂！ 题目描述

力扣题目链接

给你一个链表的头节点 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
输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

涉及算法

这道题目属于简单题型，涉及到数据结构中的链表。对于链表我们要知道以下内容：

链表是通过指针串联在一起的线性数据结构。在链表的每个节点中，由两部分组成，即数据域（存放数据）和指针域（指向下一个节点的指针）；链表的头节点没有前驱节点；链表中最后一个节点的指针域指向NULL（空指针）链表删除元素的方法，不用向数组那样，需要从后向前移动的覆盖的 *** 作。只需要将被删除节点的前一个节点的指针指向被删除节点的后一个节点。（如下图）

那么根据题目，我们可以提炼的关键点：

链表的头节点 head已知删除等于val的值，并返回新的头结点

这道题目是一个比较简单的删除 *** 作。本文有两个思路来做这道题目。

题目解答 Java题解一

这道题目是简单的删除等于val值节点的 *** 作，那么最主要的就是遍历链表，找出来值等于val的节点，然后使用链表的删除 *** 作就行了。那最容易想的方法就是从表头到表尾一个一个的比较了，然后删除对应的节点就可以了。但是我们需要注意的是，头结点是没有前驱节点的，因此对于头结点满足条件的情况需要进行单独考虑。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        
        //链表的头结点就满足条件，删除头结点
        while(head != null && head.val == val){
            head = head.next;
        }

        //删除非头结点（头结点不满足条件）
        ListNode cur = head;
        while(cur != null && cur.next !=null){
            if(cur.next.val == val){ //当前值满足条件，进行删除 *** 作
               ListNode temp;
               temp = cur.next;
               cur.next = temp.next; 
            }else{
                cur = cur.next; //当前值不满足条件，继续向后遍历
            }
        }
        return head; //返回头结点
    }
}

Java题解二

上面是对于头节点和非头节点的删除 *** 作进行了分别的考虑，那能不能是它们的删除 *** 作统一呢？
答案是可以的，那根据前面的想法，就是想办法让头结点有一个前驱节点，这样的话，直接按照正常的删除方式删除满足条件的值了。这就是虚拟节点的方式，我们定一个节点，让其作为头节点的前驱节点。

class Solution {
    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 temp = cur.next;
                cur.next = temp.next;
                            
            }else{
                cur = cur.next; //不满足条件，继续向后遍历
            }
        }
        head = dummyHead.next; //返回的是原来的链表，头节点换回来
        return head;
    }
}