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

Leetcodes刷题之删除链表的倒数N个结点和删除链表的中间的结点

吾心信其可行,则移山填海之难,终有成功之日。                           --孙中山
目录

🍉一.删除链表的倒数N个结点

🌻1.双指针

🍁2.求链表的长度

🌸二.删除链表的中间的结点


🍉一.删除链表的倒数N个结点

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

示例 1:

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]

示例 2:

输入:head = [1], n = 1
输出:[]

示例 3:

输入:head = [1,2], n = 1
输出:[1]

做题链接

🌻1.双指针

这题我们同样使用双指针的方法,我们先定义一个fast指针和slow指针,它们都指向head。

第一步:先判断fast为不为空,不为空,n就减1,fast再走一步。依次循环,直到n减到0,即退出循环。
第二步:然后slow指针和fast再同时移动,直到fast走到链表的尾,此时slow即要找到的指针,即要删除的指针。


但是这样做只是找到你要删除的结点,这题你不仅要找到倒数的N个结点,还要把这个结点的前后结点给链接起来。 

大体方法还是这个方法,但是可能fast和slow初始指向链表的位置不同,这题我们创建一个哨兵位的头结点来实现开始fast和slow指针指向phead,我们还是通过画图来理解。


直接上代码: 

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));phead->next = head;struct ListNode* fast = phead, * slow = phead;while (n--){fast = fast->next;//fast先走}while (fast->next){fast = fast->next;//此时两个指针遍历链表slow = slow->next;}slow->next = slow->next->next;struct ListNode* next = phead->next;//保存哨兵位的下一个结点free(phead);//释放哨兵结点return next;
}

这题的难点就是该如何把要删除结点的前后结点链接起来,这就需要仔细的把fast和slow初始的位置给放对才行。

🍁2.求链表的长度

我们先创建一个函数遍历链表,把链表的长度len给算出来。也是和上面一样,我们还是创建一个哨兵位的头结点phead,然后使用一个cur指针指向phead,然后cur走len-n个结点,就找到了要删除结点的前一个结点,然后cur->next=cur->next->next即可

int longlinked(struct ListNode*head)
{int len=0;while(head){len++;head=head->next;}return len;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{int len=longlinked(head);struct ListNode*phead=(struct ListNode*)malloc(sizeof(struct ListNode));phead->next=head;struct ListNode*cur=phead;int i=0;while(i<len-n){cur=cur->next;i++;}cur->next=cur->next->next;struct ListNode*second=phead->next;free(phead);phead=NULL;return second;
}

🌸二.删除链表的中间的结点

给你一个链表的头节点head 。删除 链表的中间节点 ,并返回修改后的链表的头节点head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点(下标从 0 开始),其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

  • 对于 n = 1、2、3、4 和 5 的情况,中间节点的下标分别是 0、1、1、2 和 2 。

示例 1:

输入:head = [1,3,4,7,1,2,6]
输出:[1,3,4,1,2,6]
解释:
上图表示给出的链表。节点的下标分别标注在每个节点的下方。
由于 n = 7 ,值为 7 的节点 3 是中间节点,用红色标注。
返回结果为移除节点后的新链表。 

示例 2: 

 

输入:head = [1,2,3,4]
输出:[1,2,4]
解释:
上图表示给出的链表。
对于 n = 4 ,值为 3 的节点 2 是中间节点,用红色标注。

 示例 3:

输入:head = [2,1]
输出:[2]
解释:
上图表示给出的链表。
对于 n = 2 ,值为 1 的节点 1 是中间节点,用红色标注。
值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。

做题链接

之前我们就写了找中间结点的链表题,但是上次那个只是找到中间结点即可,使用快慢指针来实现,这题就是那个题的变形,找到中间结点给删除掉,然后把中间结点的前后给链接起来,我们同样是创建一个哨兵位的结点,然后使用快慢指针来实现。fast指针指向head,而slow指针指向phead。

当fast指向链表的尾时,slow这时指向中间结点的前一个,然后链接起来就是。

struct ListNode* deleteMiddle(struct ListNode* head){if(head->next==NULL)return NULL;struct ListNode*phead=(struct ListNode*)malloc(sizeof(struct ListNode));phead->next=head;struct ListNode*fast=head,*slow=phead;  while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}slow->next=slow->next->next;struct ListNode*next=phead->next;free(phead);phead=NULL;return next;
}

相关文章:

Leetcodes刷题之删除链表的倒数N个结点和删除链表的中间的结点

吾心信其可行&#xff0c;则移山填海之难&#xff0c;终有成功之日。 --孙中山 目录 &#x1f349;一.删除链表的倒数N个结点 &#x1f33b;1.双指针 &#x1f341;2.求链表的长度 &#x1f338;二.删除链表的中间的结点 &#x1f349;一.删除链…...

Java-数据结构-并查集<二>

一.并查集的简单介绍 二. 并查集的主要构成和实现方式 三.HashMap模板和数组模板 由于在下文的模板基本一致&#xff0c;不再每次都罗列&#xff0c;大体的模板如下&#xff0c;若有错误可以在leetcode找到对应的题目解答&#xff0c;已经附上连接。 HashMap class UnionFi…...

JSP网上教学资源共享系统(源代码+论文)

通过网上教学资源共享系统的建设&#xff0c;完成了对于操作系统课程的远程化授课。可以使学生不受时间空间的限制&#xff0c;通过网络对于这门课程进行学习。建立起了基于B/C的网络化教学系统。本网站采用当前最流行的JSP网络编程技术&#xff0c;可以实现数据的高效、动态、…...

QT C++入门学习(1) QT Creator安装和使用

Qt官方下载 Qt 官网有一个专门的资源下载网站&#xff0c;所有的开发环境和相关工具都可以从这里下载&#xff0c;具体地址是&#xff1a;http://download.qt.io/ 进入链接后&#xff0c;是一个文件目录&#xff0c;依次进入这个路径&#xff1a;archive/qt/5.12/5.12.9/qt-o…...

UE动画状态机的事件触发顺序测试

正常A状态过渡到B状态的事件顺序&#xff1a; 整个流程为&#xff1a; 调用B状态的On Become Relevant事件调用B状态的On Update事件调用A状态的Left State Event事件调用B状态的Entered State Event事件调用B状态的Start Transition Event事件调用B状态的End Transition Even…...

数学建模的搜索技巧

你真的会使用“度娘”吗&#xff1f;是不是在查找所需要的东西的时候&#xff0c;搜出来的信息价值并不是很大&#xff0c;跟着北海老师学习&#xff0c;如何更高效的使用百度去查询自己想要的&#xff0c;有用的资料&#xff01; 搜索技巧 完全匹配搜索 : 查询词的外边加上双…...

学成在线笔记+踩坑(10)——课程搜索、课程发布时同步索引库。

导航&#xff1a; 【黑马Java笔记踩坑汇总】JavaSEJavaWebSSMSpringBoot瑞吉外卖SpringCloud黑马旅游谷粒商城学成在线牛客面试题_java黑马笔记 目录 1 【检索模块】需求分析 1.1 全文检索介绍 1.2 业务流程 1.2.1、课程发布时索引库里新增一条记录 1.2.2、课程搜索 2 准…...

某应用虚拟化系统远程代码执行

漏洞简介 微步在线漏洞团队通过“X漏洞奖励计划”获取到瑞友天翼应用虚拟化系统远程代码执行漏洞情报(0day)&#xff0c;攻击者可以通过该漏洞执行任意代码&#xff0c;导致系统被攻击与控制。瑞友天翼应用虚拟化系统是基于服务器计算架构的应用虚拟化平台&#xff0c;它将用户…...

solaris-Oracle11g于linux-mysql相连

Oracle11g(solaris64sparc)mysql(linux)实验 此实验目的,实现公司ebs R12 连mysql上的短信平台.预警和提示ebs中信息, 一,环境 主机名 ip 平台 数据库 dbname ebs234 192.168.1.234 …...

大厂齐出海:字节忙种草,网易爱社交

配图来自Canva可画 随着国内移动互联网红利逐渐触顶&#xff0c;互联网市场日趋饱和&#xff0c;国内各互联网企业之间的竞争便愈发激烈起来。在此背景下&#xff0c;广阔的海外市场就成为了腾讯、阿里、字节、京东、拼多多、百度、网易、快手、B站等互联网公司关注和争夺的重…...

几个实用的正则表达式

1到100之间的正整数正则 表达式&#xff1a;^[1-9]\d?$|^100$ 解释&#xff1a; ^表示匹配字符串开始位置 [1-9]表示数字1-9中的任意一个 \d表示任意一个数字 ?表示前面一个字符或子表达式出现0或1次 $表示匹配字符串结束位置 |表示或 最终的解释为&#xff1a;匹配满…...

python实战应用讲解-【numpy数组篇】常用函数(八)(附python示例代码)

目录 Python Numpy MaskedArray.cumprod()函数 Python Numpy MaskedArray.cumsum()函数 Python Numpy MaskedArray.default_fill_value()函数 Python Numpy MaskedArray.flatten()函数 Python Numpy MaskedArray.masked_equal()函数 Python Numpy MaskedArray.cumprod()函…...

Speech and Language Processing-之N-gram语言模型

正如一句老话所说&#xff0c;预测是困难的&#xff0c;尤其是预测未来。但是&#xff0c;如何预测一些看起来容易得多的事情&#xff0c;比如某人接下来要说的几句话后面可能跟着哪个单词。 希望你们大多数人都能总结出一个很可能的词是in&#xff0c;或者可能是over&#x…...

【AI】Python 安装时启用长路径支持

文章目录 场景&#xff1a;解释&#xff1a;关于文件长路径&#xff1a;计算方法&#xff1a; 场景&#xff1a; Python 安装时&#xff0c;会出现 Disable path length limit 的提示。 解释&#xff1a; 在 Windows 操作系统中&#xff0c;文件路径的长度是有限制的。在早期…...

深入理解Go语言中的接口编程【17】

文章目录 接口接口接口类型为什么要使用接口接口的定义实现接口的条件接口类型变量值接收者和指针接收者实现接口的区别值接收者实现接口指针接收者实现接口下面的代码是一个比较好的面试题 类型与接口的关系一个类型实现多个接口多个类型实现同一接口接口嵌套 空接口空接口的定…...

“数字中国·福启海丝”多屏互动光影艺术秀27日在福州举办

作为深化“数字海丝”的核心区、海上丝绸之路的枢纽城市&#xff0c;为喜迎第六届数字中国建设峰会盛大召开之际&#xff0c;福州市人民政府特此举办“数字中国福启海丝”多屏互动光影秀活动。本次光影秀活动是由福建省文化和旅游厅指导&#xff0c;福州市人民政府主办&#xf…...

Docker安装mysql8.0文档

第一步需要安装Docker基础环境&#xff0c;具体可以看看这篇 docker基础篇 第二步&#xff0c;拉取mysql8.0的镜像 docker pull mysql:8.0 第三步&#xff0c;镜像启动和文件挂载 复制下面命令执行&#xff0c;33006是对外访问暴露的端口&#xff0c;当然你也可以设置为3306…...

在函数中使用变量

shell脚本编程系列 向函数传递参数 函数可以使用标准的位置变量来表示在命令行中传给函数的任何参数。其中函数名保存在$0变量中&#xff0c;函数参数则依次保存在$1、$2等变量当中&#xff0c;也可以使用特殊变量$#来确定参数的个数 在脚本中调用函数时&#xff0c;必须将参…...

python算法中的深度学习算法之自编码器(详解)

目录 学习目标: 学习内容: 自编码器 Ⅰ. 编码器(Encoder) Ⅱ. 解码器(Decoder)...

Python入门(一)Python概述与环境搭建

Python概述与环境搭建 1.概述1.1版本及下载1.2 Python 特点 2.环境搭建3.第一个程序“hello&#xff0c;world”4.可能会存在的问题 1.概述 Python 是一个高层次的结合了解释性、编译性、互动性和面向对象的脚本语言。 Python 的设计具有很强的可读性&#xff0c;相比其他语言…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)

cd /home 进入home盘 安装虚拟环境&#xff1a; 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境&#xff1a; virtualenv myenv 3、激活虚拟环境&#xff08;激活环境可以在当前环境下安装包&#xff09; source myenv/bin/activate 此时&#xff0c;终端…...

32位寻址与64位寻址

32位寻址与64位寻址 32位寻址是什么&#xff1f; 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元&#xff08;地址&#xff09;&#xff0c;其核心含义与能力如下&#xff1a; 1. 核心定义 地址位宽&#xff1a;CPU或内存控制器用32位…...