当前位置: 首页 > 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;即使出现异常错误也不认为…...

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

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

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...