一、题干
🔗力扣203. 移除链表元素
二、题解
1、思路
题干的意思是，要删除链表中所有指定的元素。最暴力的方法是，依次遍历链表中的各个节点，并挨个调用“删除第一次出现关键字为key的节点”的方法remove()：
//删除第一次出现关键字为key的节点 public void remove(int key) { //排除特殊情况 if(head == null) { return; } if(head.val == key) { head = head.next; return; } //遍历链表 Node cur = head; while(cur.next != null) { //寻找待删除元素的第一个 if(cur.next.val == key) { break; } cur = cur.next; } //特殊情况判断 if(cur.next == null) { return; } //删除元素 cur.next = cur.next.next; }
这样的思路实现后，代码的时间复杂度是O(n²)。
如果我们只遍历一遍链表，用时间复杂度是O(n)的思路，该如何实现呢？
我们可以引入一个新的“跟屁虫”引用变量pre，记录用于遍历的引用变量cur的前一个结点地址。通过pre的协助，完成删除单链表中所有指定元素的效果。
如图，初始状态下，pre的起点为head，而cur的起点为head.next。pre此时正是cur的前一个结点。
在遍历链表的过程中，通过比较 cur.val 与 key来寻找待删除的元素key。如果cur.val != key，那么cur与pre均需接着向前走，跟屁虫pre仍然记录cur的前一个结点位置。
cur走到上图这个位置时，cur.val 就与key相等了。也就是说，cur找到了一个要删除的结点。此时，我们将cur所指向的结点删除。这时pre的巨大作用便体现出来了：
将pre.next直接指向cur.next，此时的cur所指向的结点便成功地排除在链表之外了。完成这一步后，再让cur向后走。
注意，当cur.val == key时，我们完成remove操作后只需要让cur向后走就行，pre先不急着跟上。这是因为可能存在有两个待删元素连续的情况。如下图所示：
第一个val为6的结点已经被删除，而它后面还是一个val为6的结点，也应该被删除。此时pre不跟上，pre.next = cur.next依旧可以完成删除操作。
而若pre依然跟上：
cur.next无法接回原链表，删除失败，会出现混乱。
当所有结点都遍历完毕也即cur == null后，循环结束。
因此，一般情况下的代码即是：
//起始 Node cur = head.next; Node pre = head; while(cur != null) { //是要删除的元素 if(cur.val == key) { //删除操作 pre.next = cur.next; //只有cur向后走 cur = cur.next; } else { //不是要删除的元素 //pre和cur都向后走，且pre指向cur的前一个 pre = cur; cur = cur.next; } }
特殊情况有两个：
1、链表为空，head为null。此时若直接执行cur = head.next，会抛出空指针异常。因此需要单独考虑。
2、head结点的val恰好是key。此时，有两种处理方式：
①方式1，在起始开始前，加入如下代码：
//方式1 while(head.val == key){ head = head.next; } //起始 Node cur = head.next; Node pre = head; while(cur != null) { ... }
②方式2，在遍历完链表后面的所有元素之后，再加入如下代码：
//起始 Node prev = head; Node cur = head.next; while (cur != null) { ... } //方法2 if(head.val == key) { head = head.next; }
2、完整代码
//删除所有值为key的节点 public void removeAllKey(int key) { //特殊情况处理：链表为null if(head == null){ return; } //起始 Node cur = head.next; Node pre = head; while(cur != null) { if(cur.val == key) { pre.next = cur.next; cur = cur.next; } else { pre = cur; cur = cur.next; } } //如果头结点中的值恰好是要删除的值 if(head.val == key) { head = head.next; } }
