力扣由浅至深 每日一题.22 移除链表元素

迄今为止的生命里

           —— 24.4.4

移除链表元素

给你一个链表的头节点 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

方法一:递归

思路与算法 

  链表的定义具有递归的性质,因此链表题目常可以用递归的方法求解。这道题要求删除链表中所有节点值等于特定值的节点,可以用递归实现。

对于给定的链表,首先对除了头节点 head 以外的节点进行删除操作,然后判断 head 的节点值是否等于给定的 val。如果 head 的节点值等于 val ,则 head 需要被删除,因此删除操作后的头节点为 head.next;如果 head 的节点值不等于 val,则 head 保留,因此删除操作后的头节点还是 head。上述过程是一个递归的过程。

递归的终止条件是 head 为空,此时直接返回 head。当 head 不为空时,递归地进行删除操作,然后判断 head 的节点值是否等于 val 并决定是否要删除 head。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        head.next = removeElements(head.next, val);
        if(head.val == val){
            return head.next;
        }else{
            return head;
        }
    }
}

复杂度分析

时间复杂度:O(n),其中 n 是链表的长度。递归过程中需要遍历链表一次。

空间复杂度:O(n),其中 n 是链表的长度。空间复杂度主要取决于递归调用栈,最多不会超过 n 层。

方法二:迭代

思路与算法

也可以用迭代的方法删除链表中所有节点值等于特定值的节点。

temp表示当前节点。如果 temp 的下一个节点不为空且下一个节点的节点值等于给定的 val,则需要删除下一个节点。删除下一个节点可以通过以下做法实现:

temp.next=temp.next.next
如果 temp 的下一个节点的节点值不等于给定的 val,则保留下一个节点,将 temp 移动到下一个节点即可。

当 temp 的下一个节点为空时,链表遍历结束,此时所有节点值等于 val 的节点都被删除。

具体实现方面,由于链表的头节点 head 有可能需要被删除,因此创建哑节点 dummyHead,令 dummyHead.next=head,初始化 temp=dummyHead,然后遍历链表进行删除操作。最终返回 dummyHead.next 即为删除操作后的头节点。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
            } else {
                temp = temp.next;
            }
        }
        return dummyHead.next;
    }
}

 复杂度分析

  • 时间复杂度:O(n),其中 n 是链表的长度。需要遍历链表一次。

  • 空间复杂度:O(1)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515075.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【子集回溯】Leetcode 78. 子集 90. 子集 II

【子集回溯】Leetcode 78. 子集 90. 子集 II 78. 子集90. 子集 II ---------------&#x1f388;&#x1f388;78. 子集 题目链接&#x1f388;&#x1f388;------------------- 78. 子集 class Solution {List<List<Integer>> result new ArrayList<>()…

基于约束求解器对“火影忍者Online”进行智能布阵

文章目录 1. 游戏背景2. 确定决策边界3. 布阵数据3.1 追击状态3.2 角色信息3.3 个性化要求 4. 智能布阵模型4.1 主要的决策变量4.2 约束条件&#xff08;含辅助决策变量&#xff09;4.3 目标函数及求解 1. 游戏背景 今天将以“火影忍者Online”为案例&#xff0c;写一个智能布…

STM32工程 如何设置堆栈大小(Heap和Stack)

方法1&#xff1a;通过CubeMX、CubeIDE 配置 方法2&#xff1a;直接在启动文件中修改 &#xff08;适合所有Keil工程&#xff09; Heap、Stack的值大小&#xff0c;不管使用哪种开发环境&#xff0c;它俩都肯定在启动文件中。 可以通过CtrlF&#xff0c;搜索: Heap&#xff0…

【Linux】从零认识文件操作

送给大家一句话&#xff1a; 要相信&#xff0c;所有的不美好都是为了迎接美好&#xff0c;所有的困难都会为努力让道。 —— 简蔓《巧克力色微凉青春》 开始理解基础 IO 吧&#xff01; 1 前言2 知识回顾3 理解文件3.1 进程和文件的关系3.2 文件的系统调用openwrite文件 fd 值…

STL常用容器(2)---vector容器

1.1 vector基本概念 功能&#xff1a; vector数据结构和数组非常相似&#xff0c;也称为单端数组 vector与普通数组区别&#xff1a; 不同之处在于数组是静态空间&#xff0c;而vector可以动态扩展 动态扩展&#xff1a; 并不是在原空间之后的续接的新空间&#xff0c;而…

如何从 Android 和 iPhone 中的 SIM 卡恢复已删除的联系人 [新]

在手机上&#xff0c;我们经常添加联系人&#xff0c;而很少关心联系人是存储在SIM卡中还是手机中。当我们错误删除SIM卡联系人&#xff0c;或者不当取出插入的SIM卡插入新手机时&#xff0c;那些因业务需要而添加的联系人就会消失。这可能会令人沮丧和困惑。因此&#xff0c;您…

UniApp 应用发布到苹果商店指南

&#x1f680; 想要让你的 UniApp 应用在苹果商店亮相吗&#xff1f;别着急&#xff0c;让我来带你一步步完成这个重要的任务吧&#xff01;在这篇博客中&#xff0c;我将详细介绍如何将 UniApp 应用顺利发布到苹果商店&#xff0c;让你的应用跻身于苹果生态之中。 引言 &…

Python向带有SSL/TSL认证服务器发送网络请求小实践(附并发http请求实现asyncio+aiohttp)

1. 写在前面 最近工作中遇到这样的一个场景&#xff1a;给客户发送文件的时候&#xff0c;为保证整个过程中&#xff0c;文件不会被篡改&#xff0c;需要在发送文件之间&#xff0c; 对发送的文件进行签名&#xff0c; 而整个签名系统是另外一个团队做的&#xff0c; 提供了一…

银行数字化转型导师坚鹏:银行数字化转型必知的3大客户分析维度

银行数字化转型需要进行客户分析&#xff0c;如何进行客户分析呢&#xff1f;银行数字化转型导师坚鹏认为至少从客户需求分析、客户画像分析、客户购买行为分析3个维度进行客户分析。 1.客户需求分析 银行数字化转型需要了解客户需求&#xff0c;不同年龄段的客户有不同的需求…

游戏APP如何提高广告变现收益的同时,保证用户留存率?

APP广告变现对接第三方聚合广告平台主要通过SDK文档对接&#xff0c;一些媒体APP不具备专业运营广告变现的对接能力和资源沉淀&#xff0c;导致APP被封控&#xff0c;设置列入黑名单&#xff0c;借助第三方聚合广告平台进行商业化变现是最佳选择。#APP广告变现# 接入第三方平台…

VGG网络模型

VGG网络模型 VGG的网络架构VGG16VGG19 特点总结时间关系AlexNet和VGG相似之处AlexNet和VGG不同之处启发与影响总结 VGG&#xff08;Visual Geometry Group&#xff09;是由牛津大学的 Visual Geometry Group 提出的一个深度卷积神经网络模型&#xff0c;它在2014年的ImageNet大…

哲♂学家带你深♂入了解动态顺序表

前言&#xff1a; 最近本哲♂学家学习了顺序表&#xff0c;下面我给大家分享一下关于顺序表的知识。 一、什么是顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构&#xff0c;一般情况下采用数组存储。在数组 上完成数据的增删查改。 顺序表&#xff…

动态规划刷题(算法竞赛、蓝桥杯)--乌龟棋(线性DP)

1、题目链接&#xff1a;[NOIP2010 提高组] 乌龟棋 - 洛谷 #include <bits/stdc.h> using namespace std; const int M41; int f[M][M][M][M],num[351],g[5],n,m,x; //f[a][b][c][d]表示放a个1b个2c个3d个4的总得分 int main(){scanf("%d %d",&n,&m)…

创新指南|贝恩的产品经理RAPID框架:解决问题的分步指南,使决策过程既高效又民主

您是否曾发现自己陷入项目的阵痛之中&#xff0c;决策混乱、角色不明确、团队成员之间的冲突不断升级&#xff1f;作为产品经理&#xff0c;驾驭这艘船穿过如此汹涌的水域可能是令人畏惧的。应对这些挑战的关键在于采用清晰、结构化的决策方法。输入贝恩的 RAPID 框架&#xff…

软件测试用例(2)

具体的设计方法 -- 黑盒测试 因果图 因果图是一种简化的逻辑图, 能直观地表明程序的输入条件(原因)和输出动作(结果)之间的相互关系. 因果图法是借助图形来设计测试用例的一种系统方法, 特别适用于被测试程序具有多种输入条件, 程序的输出又依赖于输入条件的各种情况. 因果图…

Linux-进程概念

1. 进程基本概念 书面概念&#xff1a;程序的一个执行实例&#xff0c;正在执行的程序等 内核概念&#xff1a;担当分配系统资源&#xff08;CPU时间&#xff0c;内存&#xff09;的实体。 2. 描述和组织进程-PCB PCB&#xff08;process contral block&#xff09;&#xff0…

【讲解下如何Stable Diffusion本地部署】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

20240324-2-频繁模式FrequentPattern

频繁模式(frequent pattern) 频繁模式一般是指频繁地出现在数据集中的模式。这种频繁模式和关联规则是数据挖掘中想要挖掘的知识。我们都知道一个很有趣的故事&#xff0c;就是啤酒和尿布的故事&#xff0c; 在某些特定的情况下&#xff0c;“啤酒”与“尿布”两件看上去毫无关…

SCP 从Linux快速下载文件到Windows本地

需求&#xff1a;通过mobaxterm将大文件拖动到windows本地速度太慢。 环境&#xff1a;本地是Windows&#xff0c;安装了Git。 操作&#xff1a;进入文件夹内&#xff0c;鼠标右键&#xff0c;点击Git Bash here&#xff0c;然后输入命令即可。这样的话&#xff0c;其实自己本…

java农家乐旅游管理系统springboot+vue

实现了一个完整的农家乐系统&#xff0c;其中主要有用户表模块、关于我们模块、收藏表模块、公告信息模块、酒店预订模块、酒店信息模块、景区信息模块、景区订票模块、景点分类模块、会员等级模块、会员模块、交流论坛模块、度假村信息模块、配置文件模块、在线客服模块、关于…