题目
题目来源leetcode
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
本地调试代码：
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{ //业务代码(leetcode核心方法代码) public ListNode removeElements(ListNode head, int val) { ... } public static void main(String[] args) { ListNode node7 = new ListNode(6, null); ListNode node6 = new ListNode(5, node7); ListNode node5 = new ListNode(4, node6); ListNode node4 = new ListNode(3, node5); ListNode node3 = new ListNode(6, node4); ListNode node2 = new ListNode(2, node3); ListNode node1 = new ListNode(1, node2); ListNode listNode = new Solution().removeElements(node1, 6); printList(listNode);//打印节点 } private static void printList(ListNode listNode) { if(listNode == null){ return; } System.out.print("["); while(listNode != null){ System.out.print(listNode.val); if(listNode.next != null){ System.out.print(","); } listNode = listNode.next; } System.out.print("]"); } }
题解
NO1：暴力解法
上来没有啥思路，直接就先暴力解法走一波，先把程序跑一遍。
思路：创建一个新节点，遍历原有的链表将其中!=的值重新创建链表节点进行挂载到新节点的next上去，最终返回新节点。
这种方式就是有点麻烦需要考虑多种情况，并且会频繁的创建新的链表，具体细节可见下面注释。
代码：
public ListNode removeElements(ListNode head, int val) { //头节点为null或者头节点的next节点为null以及当前节点==val(一个节点情况下)，返回null if(head == null || (head.next == null && head.val == val)){ return null; } //一个或多个节点情况下 ListNode newHeadNode = null; //若是第一个节点!=val构建出来一个实例 if(head.val != val){ newHeadNode = new ListNode(head.val,null); } //当前节点、前置节点 ListNode curNode = newHeadNode; ListNode nextNode = head.next; //遍历链表 while(nextNode!=null){ if(nextNode.val != val){ //处理之前第一个节点val!=的情况，针对于newHeadNode if(newHeadNode == null){ newHeadNode = new ListNode(nextNode.val,null); curNode = newHeadNode; }else{ //之后将一些!=的数据重新创建对象挂载到新组成的节点上去 curNode.next = new ListNode(nextNode.val,null);; curNode = curNode.next; } } nextNode = nextNode.next; } return newHeadNode; }
NO2：设置虚拟节点
暴力解法通过了之后，我就去看了一下其他题解的思路，相对于之前暴力法总感觉缺了点什么导致让我的代码判断条件(第一个!=val的节点情况)有这么多，其中设置虚拟节点的方式我觉得能够很好的解决我上面的问题。
思路：设置一个虚拟节点(核心)，将原本的head头节点成为其后置节点，同样在这里设置一个前置节点以及之后遍历链表的节点(每次遍历都会进行更新)，每次遍历的节点去进行判断是否=val，对前置节点的next进行替换。最终返回的就是虚拟节点的next指向的节点。
代码：
//设置虚拟节点 public ListNode removeElements(ListNode head, int val) { //节省内存消耗，这里可以提前结束方法 if(head == null){ return null; } ListNode dummy = new ListNode(-1,head); ListNode pre = dummy;//前置节点 ListNode cur = head;//循环遍历的节点 while(cur!=null){ if(cur.val == val){ pre.next = cur.next; //相当于删除当前节点 }else{ pre = cur; //移动对应的前置节点 } cur = cur.next; } return dummy.next; }
NO3：不设置虚拟节点
思路：其实与上面NO2的思路一致，只不过这里并没有直接新建出一个虚拟节点，而是在进入方法时先将head节点的所有符合元素进行剔除，使其就成为了一个虚拟节点。之后的操作与前面一致。
代码：
//不设置虚拟节点 public ListNode removeElements(ListNode head, int val) { //筛减掉不符合的元素 while(head!=null && head.val == val){ head = head.next; } if(head == null){ return null; } //当前head.val != val，我们下面可以直接对next进行遍历操作 ListNode pre = head; ListNode cur = head.next; while( cur != null){ if(cur.val == val){ pre.next = cur.next; //相当于删除操作 }else{ pre = cur; } cur = cur.next; } return head; }
