目录

一、原题再现

二、 问题分析

三、完整代码 

一、原题再现

203. 移除链表元素

难度简单1049

给你一个链表的头节点 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

 

二、 问题分析

        可以通过遍历查找，先找到包含val元素的结点。

        在单链表中想要删除一个结点，需要知道该结点的前驱结点即前一个结点。在做题过程中我们需要考虑两方面：一是cur是否指向下一个要检查的结点；二是在新链表的视角下，pre是否指向cur的前一个结点。

        因此：对于pre结点指向的修改有两种：一是cur不是指定元素的结点，此时pre正常移动（pre=cur;cur=cur.next）；二是cur是指定元素的结点,将cur指向的结点删除，cur此时pre保持不变,cur移向下一个检查结点(cur=cur.next;)

        需要注意的是，当我们在一开始定义cur和pre结点时，代码是：ListNode pre=null;ListNode cur=head;当头结点就是指定删除元素的结点时，其删除代码操作是将pre的指向指往cur下一个结点即pre.next=cur.next;此时由于pre=null，对于pre.next进行解引用操作就是出现空指针异常。

        我们可以分情况讨论，把这种情况单独写出来。但对于初学者来说，分太多种情况，会使脑子更加混乱，因此不推荐。最好的方法是将头结点变为一个普通的结点，所以可以设置一个第一个结点的前驱fakeHead结点，这是一个工具结点 ListNode fakeNode=new ListNode();使这个工具结点指向头结点。

        注意返回值是fakeHead.next。

 

三、完整代码 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
       ListNode cur=head;
        ListNode pre=null;
        ListNode fakeHead=new ListNode();//设置一个第一个结点的前驱fakeHead结点
        fakeHead.next=head;
        while(cur!=null){
            if(cur.val==val){
                //删除结点
                pre.next=cur.next;
                //如果删除结点，pre保持不变
            }
            else {
                //如果没有进行删除操作，pre=cur
                pre=cur;
            }
            cur=cur.next;
        }
        return fakeHead.next;//返回头结点
    }
}