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

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...

【WebSocket】SpringBoot项目中使用WebSocket

1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖&#xff0c;添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...

智能职业发展系统:AI驱动的职业规划平台技术解析

智能职业发展系统&#xff1a;AI驱动的职业规划平台技术解析 引言&#xff1a;数字时代的职业革命 在当今瞬息万变的就业市场中&#xff0c;传统的职业规划方法已无法满足个人和企业的需求。据统计&#xff0c;全球每年有超过2亿人面临职业转型困境&#xff0c;而企业也因此遭…...