一起刷好题|《LeetCode刷题计划》——移除链表元素（三种方法来实现） leetcode|算法|链表

文章图片

?作者简介：大家好，我是小鱼儿，大家可以叫我鱼儿
博客首页：是小鱼儿哈
系列专栏：JavaSE学习笔记
每日一句：有时候，我们做过的最艰难的选择，最终成了我们为自己做过的最棒的事。
博主也在学习阶段，如发现问题请告知，非常感谢

目录
质朴做法（要考虑特殊情况）
定义虚拟头节点来简化逻辑的做法
递归做法

废话不多说，上菜

文章图片

题目链接：力扣

质朴做法（要考虑特殊情况）分析：

我们在链表中删除一个结点其实就是让该结点没有被其他任何结点所指向，那么就需要找到该结点的前一个结点，让前一个结点不再指向下一个结点，而改为指向下下一个结点，这样就完成了对该结点的删除。

但问题又来了，如果需要删除头结点怎么办？对于头结点来说，他都没有所谓的上一个结点呀！所有说这时我们就要单独考虑了：对于删除头结点来说，我们可以直接挪动头结点，让原来头结点的下一个变成新的头结点

// 朴素做法 class Solution { public ListNode removeElements(ListNode head, int val) { if (head == null) return head; // 如果链表为空直接返回 // 处理当需要删除头结点的时候，因为正常的删除都是需要先找到要删除结点的上一个结点，所有对这种情况要进行特判 while (head.val == val && head != null) { // 因为删除头结点后，新的头结点可能还需要删除 head = head.next; if (head == null) return head; // 处理特殊情况，当链表的的最后一个元素需要被删除时 // 直接return就好，此时head为空，如果再进行head.val == key的判断就会发生空指针异常 }// 创建一个引用cur去完成链表的遍历(头节点是整个链表的灵魂,不能直接使用,避免丢失链表) // 此时的头结点绝对不是要删除的元素，所有我们可以用正常的方法进行删除 ListNode cur = head; while (cur != null && cur.next != null) { // 删除一个结点，首先要找到他的上一个结点 if (cur.next.val == val) { cur.next = cur.next.next; } else { cur = cur.next; // 继续向后走，看接下来还有没有要删除的结点 } } return head; } }

定义虚拟头节点来简化逻辑的做法分析：

此时我们不需要单独单独考虑删除头结点的那种情况了，因为此时的头结点也有着它的上一个结点：虚拟头结点

// 设置一个虚拟头结点来进行操作 class Solution { public ListNode removeElements(ListNode head, int val) { // 设置一个虚拟头结点，可以简化逻辑，这样就不用为删除头结点单独考虑了 ListNode dummyHead = new ListNode(0, head); // 调用带两个参数的构造方法，对新建的结点进行初始化，并将该结点指向链表的头结点 // 创建一个引用cur去完成链表的遍历(此时的虚拟头节点是整个链表的灵魂,不能直接使用,避免丢失链表) // 不用单独考虑链表为空的情况，应为当链表为空即cur.next == null，循环进不去，直接就返回了 ListNode cur = dummyHead; while (cur.next != null) { if (cur.next.val == val) { cur.next = cur.next.next; } else { cur = cur.next; } } return dummyHead.next; // 返回真正的头结点 } }

递归做法首先，链表可以想象成一个头结点加上它后面一个更短的结点。如图所示：

文章图片

如果头节点对应的数值不等于 val ，原问题的结果就是头节点后面挂接上子问题求得的紫色的链表，否则，结果就是子问题求得的紫色的链表。

class Solution { public ListNode removeElements(ListNode head, int val) { // 前一部分递归中递的过程，head头结点不断向后走 if (head == null) return null; // 递归出口 // 删除原链表中头节点后面值为 val 的元素的节点 // 新建一个结点引用变量ans来接受上次递归的结果，即子问题的结果 ListNode ans = removeElements(head.next, val); //递归中归的过程，在归的过程中完成了链表元素的删除 if (head.val == val) { return ans; // 如果head需要被删除，原链表头节点是上次递归后返回的待删除的节点（之前的头节点丢掉了） } else { head.next = ans; // 头结点挂上子问题（removeElements)的结果 return head; // 原链表头节点不是待删除的节点，原链表的头节点后面挂接已处理的链表（更短的 } } }

看完后你可能不太理解，那么我们来画图来实践一下：