当前位置: 首页 > news >正文

【链表OJ题(一)】移除链表元素

在这里插入图片描述

​📝个人主页:@Sherry的成长之路
🏠学习社区:Sherry的成长之路(个人社区)
📖专栏链接:数据结构
🎯长路漫漫浩浩,万事皆有期待

文章目录

  • 链表OJ题(一)
    • 1. 移除链表元素
      • 思路一-遍历
        • 一、考虑常见情况
        • 二、考虑特殊情况
          • 1.当链表的第一个结点为待移除的结点时
          • 2.当链表的最后一个结点为待移除的结点时
          • 3.当传入链表为空时
      • 思路二-尾插法
        • 一、考虑常见情况
        • 二、考虑特殊情况
          • 1.当链表的最后一个结点为待删除的结点时
          • 2.当传入链表为空时
          • 2.当要删除所有节点时
      • 思路三-强行加上一个头结点
  • 2.总结:

链表OJ题(一)

1. 移除链表元素

链接:203. 移除链表元素
题目描述:给你一个链表的头节点 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

思路一-遍历

要移除链表中值为val的结点,我们肯定是要将链表遍历一遍,关键是我们在遍历的过程中应该如何操作。我们考虑问题的时候,可以先考虑比较常见的情况,再考虑特殊情况。

一、考虑常见情况

要移除某一结点,也就是让该结点的前一个结点指向待移除结点的后一个结点,然后将待移除结点释放即可。我们可以定义3个指针变量:prev,cur,next 。

prev:记录待排查结点的前一个结点位置(previous)。
cur:记录当前正在排查的结点位置(current)。
next:记录待排查结点的后一个结点(next)。
在这里插入图片描述

当cur指针指向的结点并非待移除的结点时,3个结点依次向后移动。
在这里插入图片描述

当cur指针指向待移除的结点时,我们首先让prev指针指向的结点指向next,然后将cur指针指向的结点释放掉
在这里插入图片描述

并将next指针赋值给cur指针,next指针再后移。
在这里插入图片描述

如此进行下去,直到链表遍历完毕,那么值为val的结点也就删除了。

二、考虑特殊情况

常见情况的分析往往只能解决问题的一般情况,并不能解决问题的极端情况。要真正解决问题,我们需要考虑到问题的极端情况。例如,当待移除的结点是第一个结点或是最后一个结点的情况,当链表为空的情况。

1.当链表的第一个结点为待移除的结点时

在这里插入图片描述
这时我们需要先将头指针指向next,然后释放cur指向的结点
在这里插入图片描述
并将next指针赋值给cur指针,next指针再后移。
在这里插入图片描述

2.当链表的最后一个结点为待移除的结点时

当排查到最后一个结点时,cur指向最后一个结点,next指针指向该结点指向的位置,即NULL。
在这里插入图片描述

我们用上面常规情况的方法对其进行分析,发现常规情况的思路适用于这种特殊情况。
在这里插入图片描述
并且发现遍历的终止条件,就是当cur为NULL的时候遍历停止。
在这里插入图片描述

3.当传入链表为空时

我们可以发现,若传入的链表为空链表(NULL),cur指针的值一开始就为空,而我们遍历的终止条件就是当cur为NULL时停止遍历,所以当传入链表为空时,直接执行到函数末尾,即返回头指针(NULL)。

代码实现

struct ListNode {int val;struct ListNode *next;
};struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* prev = NULL;//记录待排查结点的前一个结点位置struct ListNode* cur = head;//记录当前正在排查的结点位置while (cur != NULL)//当cur为空时,循环停止{if (cur->val == val)//当前排查的结点是待移除的结点{struct ListNode* next = cur->next;//记录待排查结点的后一个结点位置if (cur == head)//待移除的结点是链表的第一个结点{head = next;//头指针指向nextfree(cur);//释放第一个结点cur = next;//将next指针赋值给cur指针}else//待移除的结点不是链表的第一个结点{prev->next = next;//prev指针指向的结点指向nextfree(cur);//将cur指针指向的结点释放掉cur = next;//将next指针赋值给cur指针}}else//当前排查的结点不是待移除的结点{prev = cur;//指针后移cur = cur->next;//指针后移}}return head;//返回新的头指针
}

在这里插入图片描述

思路二-尾插法

一、考虑常见情况

还可以通过遍历原链表,将不是val的值尾插到新链表newHead,这时删第一个也没有什么影响,转换成尾插的思路。
定义一个尾指针tail,第一次尾插需要赋值,newHead=tail=cur
在这里插入图片描述
cur->val!=val,尾插进新链表,再更新tail,tail->next=cur,tail=tail->next
在这里插入图片描述

cur->val==val,提前保存下一个节点,释放cur,将下一个赋值给cur
在这里插入图片描述
最后返回newHead

二、考虑特殊情况

在这里插入图片描述

1.当链表的最后一个结点为待删除的结点时

在删除最后一个(6)的时候,上一个节点tail(5)的next还指向(6),删除后就指向野指针了,所以需要tail->next=NULL
在这里插入图片描述

但如果最后一个为(7),便会拿下来尾插,tail->next!=NULL,这时不会出现野指针
在这里插入图片描述

那综合上面两种情况,不如直接置空(tail->next=NULL)吧。但运行后发现还是有问题
在这里插入图片描述

2.当传入链表为空时

在链表为空时,循环根本不会进入,所以还要加一个链表为空的判断if(head==NULL),直接return NULL,不删除了。但运行后发现还是有问题
在这里插入图片描述

2.当要删除所有节点时

若链表全是7的时候,这时所以节点都被删了,没有节点尾插了,newHead和tail还是空,又出现了野指针,所以干脆不判断链表为空,而是判断tail是否为空,若不为空,tail->next=NULL

 * Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode*newHead=NULL,*tail=NULL;struct ListNode*cur=head;while(cur){if(cur->val!=val){//尾插if(tail==NULL){newHead=tail=cur;}else{tail->next=cur;tail=tail->next;}cur=cur->next;}else{struct ListNode*next=cur->next;free(cur);cur=next;}}if(tail)tail->next=NULL;return newHead;
}

在这里插入图片描述

思路三-强行加上一个头结点

我们可能觉得思路一的代码比较复杂,当我们要移除某一个结点时,还需要判断该结点是否为第一个结点,那么有没有什么办法可以不用进行这一步操作呢?
回答是肯定的。办法就是在传入的链表前面强行加上一个头结点,并让链表原来的头指针指向该头结点,这样我们就不用判断待移除的结点是否为第一个结点了(因为现在第一个结点是头结点)。
在这里插入图片描述

在加了头结点后,我们就只需要根据常见情况的逻辑进行代码的编写即可。但是有一点不能忘记,就是在遍历完链表后要将头结点指向的位置(即第一个结点的位置)赋值给头指针,并将头结点释放掉,最后才能返回头指针。
在这里插入图片描述
代码实现

struct ListNode {int val;struct ListNode *next;
};
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));//申请一个头结点,返回其地址guard->next = head;//让头结点指向链表的第一个结点struct ListNode* cur = guard->next;//cur指针指向原链表第一个结点struct ListNode* prev = guard;//prev指针指向头结点while (cur != NULL)//当cur为空时,循环停止{if (cur->val == val)//当前排查的结点是待移除的结点{struct ListNode* next = cur->next;//记录待排查结点的后一个结点位置prev->next = next;//prev指针指向的结点指向nextfree(cur);//将cur指针指向的结点释放掉cur = next;//将next指针赋值给cur指针}else//当前排查的结点不是待移除的结点{prev = cur;//指针后移cur = cur->next;//指针后移}}head = guard->next;//将头结点指向的位置赋值给头指针,使头指针指向链表第一个结点free(guard);//释放头结点guard = NULL;//及时置空return head;//返回新的头指针
}

在这里插入图片描述

2.总结:

今天我们通过三种思路分析并完成移除链表元素这道链表OJ题目。总体来说,思路三会相较于前两个思路减少踩坑,但若是第一次遇见,也很难想到。希望我的文章和讲解能对大家的学习提供一些帮助。

当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~

在这里插入图片描述

相关文章:

【链表OJ题(一)】移除链表元素

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录链表OJ题(一)1. 移除…...

【解锁技能】学会Python条件语句的终极指南!

文章目录前言一. python条件语句的介绍1.1 什么是条件语句1.2 条件语句的语法1.3 关于内置函数bool()二. 分支语句之单分支三. 多分支语句3.1 二分支语句3.2 多分支语句3.3 嵌套循环总结前言 &#x1f3e0;个人主页&#xff1a;欢迎访问 沐风晓月的博客 &#x1f9d1;个人简介&…...

如何通过rem实现移动端的适配?

一、rem、em、vw\vh的区别&#xff1a; rem&#xff1a;参照HTML根元素的font-size em&#xff1a;参照自己的font-size vw/vh&#xff1a;将视口宽高平分100等份&#xff0c;数值就是所占比例 <!DOCTYPE html> <html lang"en"><head><meta…...

【论文阅读】-姿态识别

记录论文阅读&#xff0c;希望能了解我方向的邻域前沿吧 粗读 第一篇 ATTEND TO WHO YOU ARE: SUPERVISING SELF-ATTENTION FOR KEYPOINT DETECTION AND INSTANCE-AWARE ASSOCIATION 翻译&#xff1a;https://editor.csdn.net/md?not_checkout1&spm1001.2014.3001.5352…...

3.1 模拟栈+表达式求值

模拟栈 题目链接 栈的数组模拟非常简单&#xff0c;不详细描述 设置一个指针指向栈顶第一个元素即可 STL中stack实现已经更新在STL_Stack #include<iostream> #include<string>using namespace std;const int N1e51; int m; string s; int stack[N]; int p;//指针…...

【Python语言基础】——Python 创建表

Python语言基础——Python 创建表 文章目录 Python语言基础——Python 创建表一、Python 创建表一、Python 创建表 创建表 如需在 MySQL 中创建表,请使用 “CREATE TABLE” 语句。 请确保在创建连接时定义数据库的名称。 实例 创建表 “customers”: import mysql.connector…...

外贸建站,为什么别人的询盘更多更精准?

大多企业进行外贸建站的目的就是想要获得更多的精准询盘&#xff0c;但是具体该如何做&#xff0c;大多企业都没有方向&#xff0c;要么就是在网上看各种不系统的文章学着操作&#xff0c;要么就找个建站公司做好网站就不管了&#xff0c;而最终结果都不甚理想。那么怎样才能让…...

Gateway集成Netty服务

Gateway和Netty都有盲区的感觉&#xff1b; 一、Netty简介 Netty是一个异步的&#xff0c;事件驱动的网络应用框架&#xff0c;用以快速开发高可靠、高性能的网络应用程序。 传输服务&#xff1a;提供网络传输能力的管理&#xff1b; 协议支持&#xff1a;支持常见的数据传输…...

SpringMVC控制层private方法中出现注入的service对象空指针异常

一、现象 SpringMVC中controller里的private接口中注入的service层的bean为null&#xff0c;而同一个controller中访问修饰符为public和protected的方法不会出现这样的问题。 controller中的方法被AOP进行了代理&#xff0c;普通Controller如果没有AOP&#xff0c;private方法…...

【Unity】P4 脚本文件(基础)

Unity脚本文件&#xff08;基础&#xff09;适配的C#代码编辑器如何添加一个脚本文件获取蘑菇当前位置基础代码改变物体位置帧与帧更新前言 上一篇博文主要围绕Unity Inspector部分&#xff0c;围绕组件&#xff0c;资源文件&#xff0c;父子节点部分做介绍。 链接&#xff1a;…...

(2023版)零基础入门网络安全/Web安全,收藏这一篇就够了

由于我之前写了不少网络安全技术相关的文章和回答&#xff0c;不少读者朋友知道我是从事网络安全相关的工作&#xff0c;于是经常有人私信问我&#xff1a; 我刚入门网络安全&#xff0c;该怎么学&#xff1f; 要学哪些东西&#xff1f; 有哪些方向&#xff1f; 怎么选&#x…...

Vue3电商项目实战-登录模块2【05-登录-表单校验、06-登录-消息提示组件封装、07-登录-账户登录、08-登录-手机号登录、09-退出登录】

文章目录05-登录-表单校验06-登录-消息提示组件封装07-登录-账户登录08-登录-手机号登录09-退出登录05-登录-表单校验 文档&#xff1a;https://vee-validate.logaretm.com/v4/ 支持vue3.0 第一步&#xff1a;安装 执行命令 npm i vee-validate4.0.3 第二步&#xff1a;导入 …...

Python 中都有哪些常见的错误和异常?

本文首发自「慕课网」&#xff0c;想了解更多IT干货内容&#xff0c;程序员圈内热闻&#xff0c;欢迎关注&#xff01; 作者| 慕课网精英讲师 朱广蔚 Python 程序的执行过程中&#xff0c;当发生错误时会引起一个事件&#xff0c;该事件被称为异常。例如&#xff1a; 如果程…...

51单片机-1

1&#xff0c;单片机内部集成了CPU&#xff0c;RAM&#xff0c;ROM&#xff0c;定时器&#xff0c;中断系统&#xff0c;通讯接口等一系列电脑的常用硬件功能。单片机和计算机相比&#xff0c;单片机是一个袖珍版计算机 2&#xff0c;单片机里有中央处理器&#xff08;CPU&…...

【Azure 架构师学习笔记】-Azure Data Factory (4)-触发器详解-事件触发器

本文属于【Azure 架构师学习笔记】系列。 本文属于【Azure Data Factory】系列。 接上文【Azure 架构师学习笔记】-Azure Data Factory (3)-触发器详解-翻转窗口 前言 事件触发指的是存储事件&#xff0c;所以在新版的ADF 中&#xff0c;已经明确了是“存储事件”&#xff0c;…...

【项目设计】高并发内存池(三)[CentralCache的实现]

&#x1f387;C学习历程&#xff1a;入门 博客主页&#xff1a;一起去看日落吗持续分享博主的C学习历程博主的能力有限&#xff0c;出现错误希望大家不吝赐教分享给大家一句我很喜欢的话&#xff1a; 也许你现在做的事情&#xff0c;暂时看不到成果&#xff0c;但不要忘记&…...

2023年,35岁测试工程师只能被“优化裁员”吗?肯定不是····

国内的互联网行业发展较快&#xff0c;所以造成了技术研发类员工工作强度比较大&#xff0c;同时技术的快速更新又需要员工不断的学习新的技术。因此淘汰率也比较高&#xff0c;超过35岁的基层研发类员工&#xff0c;往往因为家庭原因、身体原因&#xff0c;比较难以跟得上工作…...

gitlab部署使用,jenkins部署使用

gitlab部署使用&#xff0c;jenkins部署使用在线安装gitlab下载gitlab安装gitlab使用gitlab设置中文修改管理员密码创建组,创建项目,创建用户jenkins下载jenkins安装jenkin使用jenkins更改管理员密码配置拉取代码配置登录gitlab拉取代码的账号密码配置项目配置gitlab仓库配置构…...

从零开始的机械臂yolov5抓取gazebo仿真(环境搭建篇下)

sunday功能包使用介绍以及开源 sunday我给自己机械臂的命名&#xff0c;原型是innfos的gluon机械臂。通过sw模型文件转urdf。Sunday项目主要由六个功能包sunday_description、sunday_gazebo、sunday_moveit_config、yolov5_ros、vacuum_plugin、realsense_ros_gazebo组成&…...

GCC编译器 MinGW的下载安装使用教程

哎 总所周知 gcc可以用来编译C 和C。在linux广泛应用&#xff0c;那么window怎么使用gcc呢。就要用到gcc的window工具----MInGW&#xff0c;安装好之后&#xff0c;直接可以在windows的dos界面编译。下面讲解安装使用过程。1.官网下载MinGW - Minimalist GNU for Windows downl…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...