《LeetCode刷题计划》——移除链表元素（三种方法来实现）

电玩女神 2024-04-23 15:37 18阅读 0赞

![ab4dfbc2ecfe4d539996a523c7f4637f.gif][]

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

**目录**

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

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

递归做法

--------------------

**废话不多说，上菜 ?**

![1407a4b378804e23a2b2216c1d918993.png][]

> **题目链接**： [力扣][Link 2]

## 质朴做法（要考虑特殊情况） ##

?**分析：**

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

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

// 朴素做法
    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; // 返回真正的头结点
        }
    }

--------------------

## 递归做法 ##

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

![7d3710ecabb54001a0fc6554c931629d.png][]

**如果头节点对应的数值不等于 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;// 原链表头节点不是待删除的节点，原链表的头节点后面挂接已处理的链表（更短的
>             }
>         }
>     }

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

![5cae80b60f6740cd9420eb152d314632.png][] 递归的确不好理解，在短短几行代码中，他看似什么都没干（其实什么都干了）

**强烈建议大家自动动手画一下递归中递和归的过程，只有你亲身画了，你才知道递归的妙处。**

![e83fb056002f4c1f8c11502a211c3cbd.png][]

[ab4dfbc2ecfe4d539996a523c7f4637f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/f41fdccc369d4d24b117c151d18b08df.gif
[Link 1]: https://blog.csdn.net/weixin_61061381?type=blog
[JavaSE]: https://blog.csdn.net/weixin_61061381/category_11724948.html?spm=1001.2014.3001.5482
[1407a4b378804e23a2b2216c1d918993.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c648fdf523224d47b61bf644f3f5ca9f.png
[Link 2]: https://leetcode-cn.com/problems/remove-linked-list-elements/
[7d3710ecabb54001a0fc6554c931629d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/57a0d8d4f9dd4c1c991e29f2e29825a9.png
[5cae80b60f6740cd9420eb152d314632.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c4f4cb6895f34e6ca2736aceaf165474.png
[e83fb056002f4c1f8c11502a211c3cbd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/4e0835e8bdd84e38990d93a7b6deb29c.png