当前位置: 首页 > 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…...

【项目实战】SpringMVC配置全局属性,是实现WebMvcConfigurer接口,还是直接继承WebMvcConfigurationSupport类?

一、说明 官方推荐以下两种方式来配置全局的SpringMVC的相关属性 方式一:实现WebMvcConfigurer接口(推荐)方式二:直接继承WebMvcConfigurationSupport类。介绍一下两者区别吧。 二、 WebMvcConfigurer介绍 WebMvcConfigurer是一个接口,用于配置全局的SpringMVC的相关属…...

房产营销、地产中介如何高效低成本获客?

数字化对企业而言&#xff0c;机遇和挑战并存。房产企业可借助数字化加强日益扩大的业务规模和业务领域管理&#xff0c;以提升管理效率&#xff0c;降低管理难度&#xff1b;基于数字化技术加强客户的服务体验&#xff0c;进而收集多业态客户和场景数据&#xff0c;拓展创新业…...

Kotlin-作用域函数

在对象的上下文中执行代码块。当您在提供lambda表达式的对象上调用这样的函数时&#xff0c;它会形成一个临时作用域。在此范围内&#xff0c;可以不带名称地访问对象。这样的函数称为作用域函数。 let run with apply also 作用域函数不会引入任何新的技术功能&#xff0c;但它…...

QNX7.1 交叉编译开源库

1.下载QNX7.1 SDK并解压 ITL:~/work/tiqnx710$ ls -l 总用量 16 drwxrwxr-x 4 xxx4096 1月 28 13:38 host -rwxrwxr-x 1 xxx 972 1月 28 13:38 qnxsdp-env.bat -rwxrwxr-x 1 xxx 1676 1月 28 13:38 qnxsdp-env.sh drwxrwxr-x 3 xxx 4096 1月 28 13:38 target xxxITL:~/work/ti…...

论文投稿指南——中文核心期刊推荐(外国语言)

【前言】 &#x1f680; 想发论文怎么办&#xff1f;手把手教你论文如何投稿&#xff01;那么&#xff0c;首先要搞懂投稿目标——论文期刊 &#x1f384; 在期刊论文的分布中&#xff0c;存在一种普遍现象&#xff1a;即对于某一特定的学科或专业来说&#xff0c;少数期刊所含…...

Fabric系列 - 链码-内部链码的特性

(1)Fabric repo下的案例 Chaincode(1.4的目录结构) fabric/examples/chaincode/go ├── example02 #一个简单的转账合约 ├── eventsender #发送事件通知 ├── passthru #调用其他链码(或者其他channel的链码)example02 (转账) 一个简单的转账合约。该链码简单实…...

NetApp SnapCenter 备份管理 ——借助应用程序一致的数据备份管理,简化混合云操作

NetApp SnapCenter 简单、可扩展、赋权&#xff1a;跨 Data Fabric 的企业级数据保护和克隆管理 主要优势 • 利用与应用程序集成的工作流和预定义策略简化备份、恢复和克隆管理。 • 借助基于存储的数据管理功能提高性能和可用性&#xff0c;并缩短测试和开发用时。 • 提供基…...

Java内置队列和高性能队列Disruptor

一、队列简介 队列是一种特殊的线性表&#xff0c;遵循先入先出、后入后出&#xff08;FIFO&#xff09;的基本原则&#xff0c;一般来说&#xff0c;它只允许在表的前端进行删除操作&#xff0c;而在表的后端进行插入操作&#xff0c;但是java的某些队列运行在任何地方插入删…...

比特数据结构与算法(第四章_下)二叉树的遍历

本章将会详细讲解二叉树遍历的四种方式&#xff0c;分别为前序遍历、中序遍历、后续遍历和层序遍历。在学习遍历之前&#xff0c;会先带大家回顾一下二叉树的基本概念。学习二叉树的基本操作前&#xff0c;需要先创建一颗二叉树&#xff0c;然后才能学习其相关的基本操作&#…...

chatGPT是什么

2022年11月&#xff0c;人工智能公司OpenAI推出了一款聊天机器人&#xff1a;ChatGPT。它能够通过学习和理解人类语言来进行对话&#xff0c;还能与聊天对象进行有逻辑的互动。除了聊天&#xff0c;ChatGPT还能够根据聊天对象提出的要求&#xff0c;进行文字翻译、文案撰写、代…...

网站开发策划案/成都计算机培训机构排名前十

问题描述项目采用: Spring Cloud Boot Gateway服务网关 Consu 注册中心在小程序发起微信支付后&#xff0c; 调用后台服务的发起微信预支付&#xff0c;通过预支付拿到的返回信息小程序在通过API调起微信支付&#xff0c; 支付成功后&#xff0c;按理支付成功后&#xff0c;…...

电商网站布局设计/网上电商平台开发

大家对于微软的Surface系列想必都已经非常熟悉了&#xff0c;但是Surface家族中还有一款大家伙&#xff0c;它自从2015年上市开始便一直处于供不应求的状态&#xff0c;这就是Surface Hub&#xff0c;一台拥有84寸屏幕的巨型平板电脑。微软Surface Hub的工程总监Peter Oehler先…...

英文b2b网站建设/网站管理和维护的主要工作有哪些

mysql中多个类型不同的字段组成一个唯一性索引&#xff0c;不会造成索引失效&#xff0c;但是如果多列字段组成的唯一性索引中有一个字段值是null&#xff0c;唯一性索引将会失效&#xff0c;采取的办法是把默认为null的值设置默认的值 建普通索引 CREATE INDEX 索引名称 ON …...

网站用什么字体做正文/如何快速提升自己

PHP类的属性不能被赋值为变量的原因 ps&#xff1a;本人亲测&#xff0c;阿里云2核4G5M的服务器性价比很高&#xff0c;新用户一块多一天&#xff0c;老用户三块多一天&#xff0c;最高可以买三年&#xff0c;感兴趣的可以戳一下&#xff1a;阿里云折扣服务器 成员属性声明时…...

中卫网站推广优化/在百度上做广告推广要多少钱

本文环境与前言之前写过一篇相关的文章:在.NET Core之前,实现.Net跨平台之MonoCentOSJexus初体验 当时的部署还是比较繁琐的,而且需要联网下载各种东西..有兴趣的可以看看,但是..已经过时了.. 虽然已经出了.NET Core2.0 但是目前是预览版本,而且部署来说 相对比较麻烦. 今天我们…...

网站本地被劫要怎么做/谷歌应用商店app下载

fastutil介绍&#xff1a; fastutil是扩展了Java标准集合框架&#xff08;Map、List、Set&#xff1b;HashMap、ArrayList、HashSet&#xff09;的类库&#xff0c;提供了特殊类型的map、set、list和queue&#xff1b; fastutil能够提供更小的内存占用&#xff0c;更快的存取速…...