移除链表元素

• 时间：2022-05-13
• 题目序号：203
• 难度：简单

问题描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

来源：力扣（LeetCode）

示例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

解题思路

题解部分参考自代码随想录。如有侵权，请联系进行删除~~

• 在链表中移除元素可以分为两种：一种是直接删除，另一种是加一个虚拟头结点
• 直接删除的话需要对头结点单独做判断，因为删除头结点和删除其他位置结点的删除规则有点差异，可以根据后面代码部分理解
• 通过添加虚拟结点（不存，next指向第一个结点），就可以统一移除规则，所有位置的结点移除规则就可以一致，但是会多出一个结点（多使用一个结点的内存空间）

• 在链表中移除元素，需要逐个遍历next结点，判断结点存储的元素是否等于val值
• 找到需要删除的结点的上一个结点，让该结点的next指向被删除结点的下一个结点（跳过当前结点，如上图所示）

注意： 在Java中不需要对删除的结点进行内存释放操作（Java有垃圾回收机制，会由虚拟机在空闲时自动释放内存），但是在C语言或需要手动释放内存的语言中，还需要手动释放掉被删除结点的内存

直接移除

• 直接移除时思想和上面基本一样，主要就是在移除头结点位置的元素时有所不同
• 一般位置元素移除需要先找到被移除结点的前一个结点，再让前一个结点直接指向被删除结点的下一个结点
• 如果需要移除头结点元素，需要直接将head后移一下即可，如上面两个图所示（Java外其他语言注意释放内存的问题）

虚拟头结点

添加虚拟头结点后，就可以让所有位置元素的移除方法都和直接删除中的一般位置元素删除方法一致

代码实现

直接删除

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 判断被删除元素是否是头结点
        while(head != null && head.val == val){
            head = head.next;   // 将head后移
        }
        // 被删除元素不是头结点
        ListNode prev = head;   // 定义指针查找被删除结点的前一个结点
        while(head != null && prev.next != null){
            if(prev.next.val == val) {
                prev.next = prev.next.next;    // 删除元素
            }
            else {
                prev = prev.next;   // 指针后移
            }
        }
        return head;
    }
}

虚拟头结点

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(-1,head);     // 定义虚拟头结点
        ListNode prev = dummyHead;   // 定义指针查找被删除结点的前一个结点
        while(prev != null && prev.next != null){
            if(prev.next.val == val) {
                prev.next = prev.next.next;    // 删除元素
            }
            else {
                prev = prev.next;   // 指针后移
            }
        }
        return dummyHead.next;
    }
}

总结

• 链表删除需要注意区分是否有虚拟头结点
• 有虚拟头结点的话在删除元素时逻辑都是一致的，无虚拟头结点需要注意对首结点进行单独判断
• 注意循环条件临界值的判断，防止出现空指针异常