203. 移除链表元素 - 力扣（LeetCode）
给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表：1->2->4->5。
分析思路：这道题的思路，与之前删除链表中重复的结点相似。
因为头结点可能被删除，因此解题的关键在于，创建一个虚结点，将虚结点的next指向原本的头结点。
题目描述：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
提示
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50
解题思路：
对于数据结构，我会采用画图进行解题。下面给大家分享一下我的解题思路，请看下图：
这是示例1的输入输出样例，上面的地址是我随便写的，只是为了让大家更好的理解数据结构。这道题还是挺简单的。
只需要让等于val值的那个结点的前一个结点的指针域改成val值结点的指针域就可以了，就可以实现逻辑上的删除，如上图中的第二个结点的指针域改成了第三个结点的指针域，因当我们遍历的时候，它会从第二个结点直接跳到第四个结点，而倒数第二个节点的指针域为null,当遍历到这时就直接停止了，就不会在遍历最后一个结点了。于是便实现了逻辑上的删除。
如下：
这样就可以删掉具有val的结点。只需要加上一些循环条件以及遇到不是val值得结点时的条件就可以了，如下：
while(cur != null){ if(cur.val == val){ prev.next = cur.next; cur = cur.next; }else{ prev = cur; cur = cur.next; } }
以上代码就可以解决很多问题。但是也有隐患，会出现一些特殊情况。
特殊情况：1.空链表 2.链表的第一个结点值是val
空链表的情况
空链表的情况处理起来很简单，直接返回null就行了。主要是是否能想到空链表的这个情况，其实对于数据结构的链表题，只要题目中不说明不可能是空链表，就要首先考虑到空链表的情况。
链表的第一个结点值是val
其实这个处理也很简单，上面那段代码可以删除第二个结点以后值是val的结点，那么就只需要在后面判断一下头节点的值是不是val，如果是val就让head = head.next 这样就可以了。
这里有一点要注意一下，判断头节点值是否为val，一定要在循环后面，也就是删除完后面节点的值是val的之后。如果在循环前判断会遇到一些问题，那就是如果第二个结点也是val，那就相当于还是没有删除头节点是val的这种情况。
class Node{ int val; Node next=null; Node(int val){ this.val=val; } public String toString(){ return String.format("(%d)", val); } //头插 public static Node pushFront(Node head,int val){ //head：原来的第一个结点，val要插入放入值 Node node=new Node(val); //把val装入一个结点中 node.next=head;//让原来的 head 成为 node 的下一个结点 head=node; //让头成为插入进去的结点 return head; //返回新的第一个结点 } //删除链表中等于定值val的所有结点 // 方法1:创建一个新链表，遍历原链表把与指定值不相等的移到新链表然后输出 public static Node removeElements1(Node head,int val){ if (head == null) { return null; } Node result = null;//创建一个新的链表的引用 Node last = null; // 记录目前 result 中的最后一个结点 Node cur = head; while (cur != null) {//这里开始遍历原链表 if (cur.val == val) { cur = cur.next; //碰见与指定值相等的直接跳过此次循环 continue; } Node next = cur.next; //记录下一次要遍历的元素 cur.next = null; //因为不知道这是不是最后一个结点，所以把这个结点的.next=null; if (result == null) { result = cur; //result指向链表的头 } else { last.next = cur; //这里是让新链表的倒数第二个结点连接最后一个结点 } last = cur; //记录最后一个结点 cur = next; //cur开始遍历下一个结点 } return result; } //方法2：直接在原链表上进行操作，由于删除一个结点必须要知道它的前驱，但是第一个结点往往是没有前驱的，所以我们在前驱问题上有可以有3种不同的实现方法 //方法2-1： public static Node removeElements2_1(Node head,int val) { if (head == null) { return null; } Node prev =null; //定义一个引用，它指向cur指向的结点的前一个结点 Node cur=head; while(cur!=null){ if (cur.val == val) { if (cur == head) { //应对cur是头的情况，直接让head指向下一个结点 head = cur.next; } else { prev.next = cur.next; //prev直接绕过要删除的结点，让它成为垃圾被回收 } } else { prev = cur;//如果不是，把prev指向cur指向的结点 } cur=cur.next; } return head; } //方法2-2：从第二个结点开始遍历，最后在应对第一个结点的情况 public static Node removeElements2_2(Node head,int val) { if (head == null) { return null; } Node prve=head; Node cur=head.next; while (cur!=null){ if(cur.val==val){ prve.next=cur.next; } else{ prve=cur; } cur=cur.next; } if(head.val==val){ //如果第一个结点就是要删除的结点，那么直接让head指向下一个结点 head=head.next; } return head; } //方法2-3：定义一个没用的结点头插到原链表里，然后打印的时候从第二个结点开始打印 public static Node removeElements2_3(Node head,int val) { if (head == null) { return null; } Node tmpHead=new Node(0); tmpHead.next=head;//头插到原链表里 Node prev=tmpHead; Node cur=head; while(cur!=null){ if(cur.val==val){ prev.next=cur.next; }else{ prev=cur; } cur=cur.next; } return head; //这里的head指向的是第二个结点 } } public class MyLinkedList { public static void main(String[] args){ Node head=null; //创建一个空链表 head=Node.pushBack(head,1); head=Node.pushBack(head,2); head=Node.pushBack(head,6); head=Node.pushBack(head,3); head=Node.pushBack(head,4); head=Node.pushBack(head,5); head=Node.pushBack(head,6); print(head); System.out.println(); Node.removeElements1(head,6); print(head) } //打印函数 private static void print(Node head){ System.out.println("打印链表"); for(Node cur=head;cur!=null;cur=cur.next) { System.out.print(cur+"-->"); } System.out.print("null"); } 在这里插入代码片
