【Leedcode】环形链表必备的面试题和证明题(附图解)
环形链表必备的面试题和证明题(附图解)
文章目录
- 环形链表必备的面试题和证明题(附图解)
- 前言
- 一、第一题
- 1.题目
- 2.思路
- 3.代码
- 4.延伸问题
- (1)证明题一:
- (2)证明题二:
- 二、第二题
- 1.题目
- 2.思路+延伸的证明题
- 总结
前言
本文介绍环形链表相关的两道面试题以及延伸出来的证明题(附源码+图解)
一、第一题
1.题目
141.环形链表 : 如下(示例):
给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。
为了表示给定链表中的环,评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从0开始).
注意:pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环 ,则返回 true 否则,返回 false


2.思路
slow和fast指向链表的开始,slow一次走一步,fast一次走两步,不带环fast就会走到空,带环fast会追上slow,如下图!

3.代码
代码如下(示例):
struct ListNode
{int val;struct ListNode *next;
};
bool hasCycle(struct ListNode *head)
{struct ListNode* slow = head , *fast = head;while(fast && fast -> next){slow = slow -> next;fast = fast -> next -> next;if(slow == fast){return true;}}return false;
}
4.延伸问题
(1)证明题一:
题目 : 如下(示例):
为什么slow和fast一定会在环中相遇?会不会在环里面错过,永远遇不上?
结论 :如下(示例):
他们一定会相遇,但需要证明!
分析证明 :如下(示例):


(2)证明题二:
题目 : 如下(示例):
为什么slow走一步,fast要走两步?能否fast一次走n步(n>2)?
结论 :如下(示例):
当n>2时,不一定会相遇,需要证明!
分析证明 :如下(示例):



二、第二题
1.题目
- 环形链表2 : 如下(示例):
给定一个链表的头节点head,返回链表开始入环的第一个节点。如果链表无环,则返回null。如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。
为了表示给定链表中的环,评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从0开始)。
如果pos是-1,则在该链表中没有环。注意:pos不作为参数进行传递,仅仅是为了标识链表的实际情况。不允许修改链表。

2.思路+延伸的证明题
思路 / 结论 : 如下(示例):
一个指针从相遇点开始走,一个指针从链表头部开始走,他们会在环的入口点相遇!
证明方法(1)如下图



证明方法(2)如下图

总结
以上就是今天要讲的内容,本文介绍了环形链表必备的面试题和证明题(附图解)
如果我的博客对你有所帮助记得三连支持一下,感谢大家的支持!

相关文章:
【Leedcode】环形链表必备的面试题和证明题(附图解)
环形链表必备的面试题和证明题(附图解) 文章目录环形链表必备的面试题和证明题(附图解)前言一、第一题1.题目2.思路3.代码4.延伸问题(1)证明题一:(2)证明题二:二、第二题1.题目2.思路延伸的证明题总结前言 …...
Vulnhub靶场----7、DC-7
文章目录一、环境搭建二、渗透流程三、思路总结一、环境搭建 DC-7下载地址:https://download.vulnhub.com/dc/DC-7.zip kali:192.168.144.148 DC-7:192.168.144.155 二、渗透流程 nmap -T5 -A -p- -sV -sT 192.168.144.155思路: …...
【Unity VR开发】结合VRTK4.0:创建滑块
语录: 只有经历地狱般的磨练,才能炼出创造天堂的力量。 前言: 滑块是一个非常简单的控件,它允许通过沿有限的驱动轴滑动 Interactable 来选择不同的值。我们将使用线性驱动器创建一个滑块控件,该控件允许我们根据与滑…...
Latex中的表格(2)
Latex中的表格一、一个加脚注的三线表的例子二、表格中加注释三、并排的表格3.1 使用小页环境并排表格3.2 使用子表格并排表格四、一个复杂的表格五、一个长表格这篇文章主要罗列一些特殊的表格例子。内容来自:一篇北师大学位论文模板,详见https://githu…...
(七)输运定理
本文主要内容包括:1. 物质积分2. 曲线上物质积分的时间变化率3. 曲面上物质积分的时间变化率4. 体积域上物质积分的时间变化率 (Reynolds 输运定理)1. 物质积分 考虑 t0t_0t0 时刻参考构型中由物质点 X⃗\vec{X}X所形成的 物质曲线 ct0c_{t_0}ct0、物质曲面 …...
ABBYYFineReader15免费电脑pdf文档文字识别软件
ABBYYFineReader是一款OCR文字识别软件,它可以对图片、文档等进行扫描识别,并将其转换为可编辑的格式,比如Word、Excel等,操作也是挺方便的。 我们在官网找到该软件并进行下载,打开软件后,选择转换为“Mic…...
顺序表(超详解哦)
全文目录引言顺序表定义静态顺序表动态顺序表动态顺序表的接口实现顺序表的初始化与销毁顺序表尾插/尾删顺序表头插/头删顺序表在pos位置插入/删除顺序表的打印顺序表中的查找总结引言 在生产中,为了方便管理数据,我们经常会需要将一些数据连续的存储起…...
Compose-Animation高级别动画
目录前言AnimatedVisibilityisScrollingUpFABscaffoldanimateContentSizeCrossfade顶部气泡下弹前言 AnimatedVisibility 驱动可视性相关动画,即布局显隐 animateContentSize 内容变换动画相关 Crossfade 布局(或者页面)切换过渡动画 Animat…...
c++11 标准模板(STL)(std::unordered_set)(八)
定义于头文件 <unordered_set> template< class Key, class Hash std::hash<Key>, class KeyEqual std::equal_to<Key>, class Allocator std::allocator<Key> > class unordered_set;(1)(C11 起)namespace pmr { templ…...
Python每日一练(20230225)
目录 1. 整数反转 2. 求最大公约数和最小公倍数 最大公约数 最小公倍数 3. 单词搜索 II 附录: DFS 深度优先搜索算法 BFS 广度优先搜索算法 BFS 和 DFS 的区别 1. 整数反转 给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。…...
基于博客系统的测试用例
登陆界面博客预览页博客详情页博客编辑页...
C语言运算符算术运算符关系运算符
C 运算符 运算符是一种告诉编译器执行特定的数学或逻辑操作的符号。C 语言内置了丰富的运算符,并提供了以下类型的运算符: 算术运算符 关系运算符 逻辑运算符 位运算符 赋值运算符 杂项运算符 本章将逐一介绍算术运算符、关系运算符、逻辑运算符、位运…...
C语言 深度剖析数据在内存中的存储
目录数据类型详细介绍整形在内存中的存储:原码,反码,补码大小端字节序介绍及判断浮点型在内存中的存储解析数据类型详细介绍整形:1.为什么char类型也会归类到整形家族当中去呢?字符存储和表示的时候本质上使用的是ASCI…...
MyBatis快速开发
查询user表中的所有数据 步骤: 创建user表 打开Navicat,新建查询,将下面SQL代码复制粘贴并执行: create database mybatis; use mybatis;drop table if exists tb_user;create table tb_user(id int primary key auto_incremen…...
大数据常见应用场景及架构改进
大数据常见应用场景及架构改进大数据典型的离线处理场景1.大数据数据仓库及它的架构改进2.海量数据规模下的搜索与检索3.新兴的图计算领域4.海量数据挖掘潜在价值大数据实时处理场景大数据典型的离线处理场景 1.大数据数据仓库及它的架构改进 对于离线场景,最典型…...
【华为OD机试模拟题】用 C++ 实现 - 挑选字符串(2023.Q1)
最近更新的博客 【华为OD机试模拟题】用 C++ 实现 - 货币单位换算(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 选座位(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 停车场最大距离(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 重组字符串(2023.Q1) 【华为OD机试模…...
程序员是世界上最理性、最睿智的群体,耶稣也反驳不了我,我说的!
有人说,程序员是吃青春饭的,35 岁就提前退休了。 猛一看,这句话是对的;仔细一看,这句话是不对的。 说它对,是因为现实中确实有很多程序员 35 岁就被毕业了;说它不对,是因为 35 岁以…...
人工智能到底是什么?
人工智能(Artificial Intelligence,AI)是一种利用计算机科学和统计学理论和技术来实现人类智能的一门交叉学科,旨在使计算机系统能够模拟、扩展和增强人类的智能能力,使计算机能够像人类一样思考、学习、决策和执行任务…...
在动态规划的海洋中遨游(三)
前言:\textcolor{Green}{前言:}前言: 💞 好久没写题,有点生疏了。这也是给大家提一个醒,一定要一直坚持下去,哪怕每天只做一点点。💞 算法类别一、算法介绍原理适用的情况做题步骤二…...
enable_if模板编程实现字节序转换模板
enable_if和SFINAESFINAE是模板的一个特性,也就是替换失败不报错。正常来说,函数匹配的时候按照优先级依次匹配定义的重载函数,最终选择最佳匹配的函数运行。模板也是一样的,但是在替换模板时,即使出现异常错误也不认为…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
安卓基础(Java 和 Gradle 版本)
1. 设置项目的 JDK 版本 方法1:通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分,设置 Gradle JDK 方法2:通过 Settings File → Settings... (或 CtrlAltS)…...
Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程
鸿蒙电脑版操作系统来了,很多小伙伴想体验鸿蒙电脑版操作系统,可惜,鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机,来体验大家心心念念的鸿蒙系统啦!注意:虚拟…...
