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

【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.题目

  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 附录&#xff1a; DFS 深度优先搜索算法 BFS 广度优先搜索算法 BFS 和 DFS 的区别 1. 整数反转 给你一个 32 位的有符号整数 x &#xff0c;返回将 x 中的数字部分反转后的结果。…...

基于博客系统的测试用例

登陆界面博客预览页博客详情页博客编辑页...

C语言运算符算术运算符关系运算符

C 运算符 运算符是一种告诉编译器执行特定的数学或逻辑操作的符号。C 语言内置了丰富的运算符&#xff0c;并提供了以下类型的运算符&#xff1a; 算术运算符 关系运算符 逻辑运算符 位运算符 赋值运算符 杂项运算符 本章将逐一介绍算术运算符、关系运算符、逻辑运算符、位运…...

C语言 深度剖析数据在内存中的存储

目录数据类型详细介绍整形在内存中的存储&#xff1a;原码&#xff0c;反码&#xff0c;补码大小端字节序介绍及判断浮点型在内存中的存储解析数据类型详细介绍整形&#xff1a;1.为什么char类型也会归类到整形家族当中去呢&#xff1f;字符存储和表示的时候本质上使用的是ASCI…...

MyBatis快速开发

查询user表中的所有数据 步骤&#xff1a; 创建user表 打开Navicat&#xff0c;新建查询&#xff0c;将下面SQL代码复制粘贴并执行&#xff1a; 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.大数据数据仓库及它的架构改进 对于离线场景&#xff0c;最典型…...

【华为OD机试模拟题】用 C++ 实现 - 挑选字符串(2023.Q1)

最近更新的博客 【华为OD机试模拟题】用 C++ 实现 - 货币单位换算(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 选座位(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 停车场最大距离(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 重组字符串(2023.Q1) 【华为OD机试模…...

程序员是世界上最理性、最睿智的群体,耶稣也反驳不了我,我说的!

有人说&#xff0c;程序员是吃青春饭的&#xff0c;35 岁就提前退休了。 猛一看&#xff0c;这句话是对的&#xff1b;仔细一看&#xff0c;这句话是不对的。 说它对&#xff0c;是因为现实中确实有很多程序员 35 岁就被毕业了&#xff1b;说它不对&#xff0c;是因为 35 岁以…...

人工智能到底是什么?

人工智能&#xff08;Artificial Intelligence&#xff0c;AI&#xff09;是一种利用计算机科学和统计学理论和技术来实现人类智能的一门交叉学科&#xff0c;旨在使计算机系统能够模拟、扩展和增强人类的智能能力&#xff0c;使计算机能够像人类一样思考、学习、决策和执行任务…...

在动态规划的海洋中遨游(三)

前言&#xff1a;\textcolor{Green}{前言&#xff1a;}前言&#xff1a; &#x1f49e; 好久没写题&#xff0c;有点生疏了。这也是给大家提一个醒&#xff0c;一定要一直坚持下去&#xff0c;哪怕每天只做一点点。&#x1f49e; 算法类别一、算法介绍原理适用的情况做题步骤二…...

enable_if模板编程实现字节序转换模板

enable_if和SFINAESFINAE是模板的一个特性&#xff0c;也就是替换失败不报错。正常来说&#xff0c;函数匹配的时候按照优先级依次匹配定义的重载函数&#xff0c;最终选择最佳匹配的函数运行。模板也是一样的&#xff0c;但是在替换模板时&#xff0c;即使出现异常错误也不认为…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...