本文主要是介绍leetcode【链表—简单】203.移除链表元素，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• 前言
• 题目
• 题解
• • NO1：暴力解法
  • NO2：设置虚拟节点
  • NO3：不设置虚拟节点
• 参考资料

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为链表专题。

题目

题目来源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;
}

参考资料

[1]. leetcode题解

[2]. 代码随想录—203.移除链表元素

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！
欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料
Q群：851968786 我们可以一起探讨学习
注明：转载可，需要附带上文章链接

这篇关于leetcode【链表—简单】203.移除链表元素的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！