leetcode【链表—简单】203.移除链表元素

2021/10/15 23:44:46

本文主要是介绍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;
}

image-20211013191857985



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;
}

image-20211013200123418



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;
}

image-20211013195919134



参考资料

[1]. leetcode题解

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



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



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


扫一扫关注最新编程教程