【链表OJ题(二)】链表的中间节点
📝个人主页:@Sherry的成长之路
🏠学习社区:Sherry的成长之路(个人社区)
📖专栏链接:数据结构
🎯长路漫漫浩浩,万事皆有期待
文章目录
- 链表OJ题(二)
- 1. 链表的中间节点
- 1.1 思路--两次遍历
- 1.2 题目附加条件
- 1.2.1 思路-快慢指针
- 2.总结:
上一篇链表OJ题链接:【链表OJ题(一)】移除链表元素
链表OJ题(二)
1. 链表的中间节点
链接:876. 链表的中间结点
描述:
给定一个头结点为 head 的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
示例1:
输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意,我们返回了一个 ListNode 类型的对象 ans,这样:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例2::
输入:[1,2,3,4,5,6]
输出:此列表中的结点 4 (序列化形式:[4,5,6])
由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。
提示:
给定链表的结点数介于 1 和 100 之间。
1.1 思路–两次遍历
因为这道题目并没有时间复杂度的规定,所以我们只需要先遍历一遍链表,统计链表当中的结点个数,然后再遍历一遍链表,寻找中间位置的结点即可。
代码实现
struct ListNode {int val;struct ListNode *next;
};struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* cur = head;//记录当前结点位置int count = 0;//记录链表中结点的总数while (cur)//遍历的停止条件{count++;//总数加一cur = cur->next;//指针后移}int mid = count / 2;//中间结点与第一个结点之间相差的结点数struct ListNode* midnode = head;//记录中间结点的位置while (mid--)//从第一个结点开始,指针后移mid个结点{midnode = midnode->next;//指针后移}return midnode;//返回中间结点
}
1.2 题目附加条件
我们可以明显知道,上面这种思路的时间复杂度是O(n2),那么我们有没有办法在只遍历一遍链表的情况下找到中间结点的位置呢?也就是要求代码的时间复杂度为O(n)
1.2.1 思路-快慢指针
既然我们要找的是中间位置的结点,那么我们可以定义两个指针,第一个指针指向当前遍历到的最后一个结点,第二个指针时刻指向已经遍历过的结点的中间结点。如此进行下去,因为第二个指针始终指向的是已经遍历过的结点的中间结点,所以当链表遍历完后直接返回第二个指针即可。这就是所谓的“快慢指针”。
寻找规律:
我们不妨定义两个指针名叫:fast,slow。
fast
:记录当前遍历到的最后一个结点。(快指针)
slow
:记录已经遍历过的结点的中间结点。(慢指针)
通过观察,我们可以发现,当slow指针走一步时,fast指针走一步或是走两步都满足slow指针指向的是已经遍历过的结点的中间结点。也就是slow指针走一步,fast指针最多可以走两步。
所以,我们可以遍历链表,当fast指针遍历到链表末尾时,就立刻返回此时的slow指针即可。
注意
:因为fast指针一次是走两步,所以当fast指针指向的内容为空或是fast指针指向的结点所指向的内容(fast->next)为空时,均停止遍历链表。
这两种情况下停止遍历,立刻返回slow指针。这样,我们就在只遍历了一遍链表的情况下找到了中间结点的位置,即时间复杂度为O(n)。
代码实现
struct ListNode {int val;struct ListNode *next;
};struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast = head;//快指针struct ListNode* slow = head;//慢指针while (fast&&fast->next)//遍历继续的条件{slow = slow->next;//慢指针一次走一步fast = fast->next->next;//快指针一次走两步}return slow;//返回慢指针
}
2.总结:
今天我们通过两种思路分析并完成链表的中间节点这道链表OJ题目,也学到了一个新的思路–快慢指针,在之后的题目中将再次出现它的使用。希望我的文章和讲解能对大家提供一些帮助。
当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~
相关文章:

【链表OJ题(二)】链表的中间节点
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯长路漫漫浩浩,万事皆有期待 文章目录链表OJ题(二)1. 链表…...

【强烈建议收藏:MySQL面试必问系列之并发事务锁专题】
一.知识回顾 上节课我们一起学习了MySQL面试必问系列之事务,没有学习的同学可以看一下上一篇文章,肯定对你会有帮助,学习过的同学肯定知道,上节课我们留了一个小尾巴,这个小尾巴是什么呢?就是没有详细展开…...

Linux下使用Makefile实现条件编译
在Linux系统下Makefile和C/C语言都有提供条件选择编译的语法,就是在编译源码的时候,可以选择性地编译指定的代码。这种条件选择编译的使用场合有好多,例如我们开发一个兼容标准版本与定制版本兼容的项目,那么,一些与需…...

java 应用cpu飙升(超过100%)故障排查
前言害。。。昨天刚写完一份关于jvm问题排查相关的博客,今天线上项目就遇到了一个突发问题。现象是用户反映系统非常卡,无法操作。然后登录服务器查看发现cpu 一直100%以上。具体排查步骤:1,首先top命令查看服务器cpu等情况&#…...

光学设计软件Ansys的Lumerical 2023版本下载与安装使用
文章目录前言一、许可管理工具安装二、许可管理器配置三、Lumerical安装四、工具使用配置总结前言 Lumerical是一款功能强大的软件,用于设计和分析从组件到系统阶段的光子学和电磁学。这个版本的Lumerical改进了电子和光子学设计工具,用于复杂光子学&am…...

Java 异常
文章目录1. 异常概述2. JVM 的默认处理方案3. 异常处理之 try...catch4. Throwable 的成员方法5. 编译异常和运行异常的区别6. 异常处理之 throws7. 自定义异常8. throws 和 throw 的区别1. 异常概述 异常就是程序出现了不正常的情况。 ① Error:严重问题ÿ…...

JavaSE学习笔记day17
零、 复习昨日 File: 通过路径代表一个文件或目录 方法: 创建型,查找类,判断类,其他 IO 输入& 输出字节&字符 try-catch代码 一、作业 给定路径删除该文件夹 public static void main(String[] args) {deleteDir(new File("E:\\A"));}// 删除文件夹public s…...

【项目】Vue3+TS 动态路由 面包屑 查询重置 列表
💭💭 ✨:【项目】Vue3TS 动态路由 面包屑 查询重置 列表 💟:东非不开森的主页 💜: 热烈的不是青春,而是我们💜💜 🌸: 如有错误或不足之处࿰…...
前脚背完这些接口自动化测试面试题,后脚就进了字节测试岗
1、请结合你熟悉的项目,介绍一下你是怎么做测试的? -首先要自己熟悉项目,熟悉项目的需求、项目组织架构、项目研发接口等 -功能 接口 自动化 性能 是怎么处理的? -第一步: 进行需求分析,需求评审&#…...
termux 安装centos
相关链接 centos官网rootfs制作其他人提供的安装脚本centos镜像列表其他人提供的安装脚本的说明 如果想使用老版本的centos7跟着上面链接5走就行 如果想用新系统比如centos9 stream,就跟我来 Q:为什么要装新系统? A:旧系统太多软件已过时,升级费时费…...

从菜鸟程序员到高级架构师,竟然是因为这个字final
final实现原理 简介 final关键字,实际的含义就一句话,不可改变。什么是不可改变?就是初始化完成之后就不能再做任何的修改,修饰成员变量的时候,成员变量变成一个常数;修饰方法的时候,方法不允…...

【vulhub漏洞复现】CVE-2018-2894 Weblogic任意文件上传漏洞
一、漏洞详情影响版本weblogic 10.3.6.0、weblogic 12.1.3.0、weblogic 12.2.1.2、weblogic 12.2.1.3WebLogic是美国Oracle公司出品的一个application server,确切的说是一个基于JAVAEE架构的中间件,WebLogic是用于开发、集成、部署和管理大型分布式Web应…...

函数栈帧详解
写在前面 这个模块临近C语言的边界,学起来需要一定的时间,不过当我们知道这些知识后,在C语言函数这块我们看到的不仅仅是表象了,可以真正了解函数是怎么调用的。不过我的能力有限,下面的的知识若是不当,还…...

Spring 事务(编程式事务、声明式事务@Transactional、事务隔离级别、事务传播机制)
文章目录1. 事务的定义2. Spring 中事务的实现2.1 MySQL 中使用事务2.2 Spring 中编程式事务的实现2.3 Spring 中声明式事务2.3.1 声明式事务的实现 Transactional2.3.2 Transactional 作用域2.3.3Transactional 参数设置2.3.4 Transactional 异常情况2.3.5 Transactional 工作…...

车载技术——Window Display之surface的绘制过程与原理
一、Surface 概述 OpenGL ES/Skia定义了一组绘制接口的规范,为什么能够跨平台? 本质上需要与对应平台上的本地窗口建立连接。也就是说OpenGL ES负责输入了绘制的命令,但是需要一个 “画布” 来承载输出结果,最终展示到屏幕。这个…...
2023年全国最新工会考试精选真题及答案10
百分百题库提供工会考试试题、工会考试预测题、工会考试真题、工会证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 51.()是企业工会的权力机关,每年召开一至两次会议。 A.会员大会 B.会…...

pytorch-复现经典深度学习模型-LeNet5
Neural Networks 使用torch.nn包来构建神经网络。nn包依赖autograd包来定义模型并求导。 一个nn.Module包含各个层和一个forward(input)方法,该方法返回output。 一个简单的前馈神经网络,它接受一个输入,然后一层接着一层地传递,…...

【C++】类和对象(上)
文章目录对象的介绍类的介绍类的两种定义方式类的访问限定符及封装访问限定符封装类的作用域类的实例化类的对象模型对象的介绍 C语言是面向过程的,关注的是过程,分析出求解问题的步骤,通过函数调用逐步解决问题; C是基于面向…...

工作中责任链模式用法及其使用场景?
前言 笔者是金融保险行业,有这么一种场景,业务员录完单后提交核保,这时候系统会对保单数据进行校验,如不允许手续费超限校验,客户真实性校验、费率限额校验等等,当校验一多时,维护起来特别麻烦…...

三八女神节有哪些数码好物?2023年三八女神节数码好物清单
2023年的三八女神节就快到了,大家还在烦恼,不知道有哪些数码好物?在此,我来给大家分享几款三八女神节实用性强的数码好物,一起来看看吧。 一、蓝牙耳机:南卡小音舱 参考价:239 推荐理由&…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...

算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...

抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...