#14环形链表#

news/2024/4/19 20:08:14/

环形链表

1°题目链接

链接

2°思路

slow和fast指向链表的开始
slow一次走一步
fast一次走两步
不带环 fast就会为空
带环 fast就会在环里追上slow

3°实现

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°运行结果

5°延伸问题

1.为什么slow和fast一定会在环中相遇?
会不会在环里面错过 永远遇不上 请证明一下
结论:一定会相遇 但需要证明

2.为什么slow走一步 fast走的两步呢?
能不能fast一次走n步(n>2) 请证明一下
结论:fast一次走n步 n>2不一定会相遇

1.
分析证明:
第一步:slow和fast fast一定是先进环 slow走了入环前距离的一半
第二步:随着slow进环 fast已经在环里面走了一段 走了多少跟环的大小一样
假设slow进环的时候 slow跟fast的距离为N 
fast开始追slow slow每次走1步 fast往前走2步 每追1次 判断一下相遇
每追1次 fast和slow的距离变化:N会自减 最后N变成0就相遇了
每追1次 距离减少1 距离最后减到0的时候就是相遇的点

2.
还是假设slow进环的时候 slow跟fast的距离为N
如果n>2的话 每走一次 距离缩短n-1步
N是n-1的倍数 第一次可以追上 
N不是n-1的倍数 第一次追不上 第二次有可能追上
如果第二次次再追不上 就永远追不上

n=3
差为2 
当N是偶数时 可以追上
当N时奇数不可以追上 但追到最后的时候 距离会变为1
再走一次 变为-1 也就等价于距离变为C-1 C是环的长度
如果C-1是偶数 可以追上
如果C-1是奇数 永远追不上
当C-1时奇数时 会重复第一次N时奇数的过程 
走到最后距离又会变为C-1 死循环 永远追不上

n=4
差为3
当N是3的倍数时 可以追上
当N不是3的倍数时 这一次不可以追上
会出现两种情况 走到最后距离是2或者1
再走一步 距离变为C-1或者C-2 C是环的长度
C-1或者C-2是3的倍数的话   就可以追上
C-1或者C-2不是3的倍数的话 就永远追不上
陷入死循环

同理的话n>2的时候 有可能追不上

#14环形链表#完


http://www.ppmy.cn/news/22018.html

相关文章

三菱Q系列QJ71C24N模块 MODBUS通信(含完整步骤+源代码)

MODBUS通信的其它相关基础知识请参看下面的文章链接: SMART S7-200PLC MODBUS通信_RXXW_Dor的博客-CSDN博客MODBUS 是 OSI 模型第 7 层上的应用层报文传输协议,它在连接至不同类型总线或网络的设备之间提供客户机/服务器通信。自从 1979 年出现工业串行链路的事实标准以来,…

Qt调用主界面ui

文章目录解决问题简易步骤1. mainwindow.h2. mainwindow.cpp3. UDPserver.h4. UDPserver.cpp头文件互相引用解决问题 为了在其他类中调用主界面MainWindow的ui。 简易步骤 1. mainwindow.h uiuiui: 设置为public #ifndef MAINWINDOW_H #define MAINWINDOW_H #include <Q…

11 |「哈希表」简析

前言 前言&#xff1a;刷「哈希表」高频面试题。 文章目录前言一、简介1、离散化1&#xff09;什么是离散化2&#xff09;离散化存储3&#xff09;离散化映射2、哈希表1&#xff09;什么是哈希表2&#xff09;哈希表存储3&#xff09;哈希函数4&#xff09;哈希冲突二、参考链接…

C++内联函数:那时我还太年轻,并不知道使用inline带来的效率,早已在暗中标好了价格

&#x1f451;专栏内容&#xff1a;C学习笔记⛪个人主页&#xff1a;子夜的星的主页&#x1f495;座右铭&#xff1a;日拱一卒&#xff0c;功不唐捐 文章目录一、前言二、内联函数1、起源2、概念三、与宏的区别1、宏的缺点2、两者区别四、内联函数的代价代价一&#xff1a;可执…

【数据结构与算法】跳表

&#x1f320;作者&#xff1a;阿亮joy. &#x1f386;专栏&#xff1a;《数据结构与算法要啸着学》 &#x1f387;座右铭&#xff1a;每个优秀的人都有一段沉默的时光&#xff0c;那段时光是付出了很多努力却得不到结果的日子&#xff0c;我们把它叫做扎根 目录&#x1f449;…

4.6--贪心--最小生成树(MST)

一共有两种方法Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。 Prim算法--选集合S中所有顶点的邻接点 距离最短的那个点&#xff08;不属于S&#xff09;加入集合S Kruskal算法--每次选取最短的且不构成回路的边 它们都利用了下面的最小生成树性质&#xf…

SpringCloud系列(九)[docker 篇] - Centos 7 下 Docker 的安装及基本操作指令

本篇文章将详细介绍 Centos 7 下 Docker 的安装以及一些基本操作指令. DockerDocker 的安装步骤Docker 基本操作指令Docker 的安装步骤 步骤一: 确保自己电脑的虚拟机联网并安装了 yum 工具, 如果没有安装 yum, 则执行下面的命令; yum install -y yum-utils \device-mapper-p…

在Ubuntu系统上Qt安装和配置

一、说明 QT界面本不应该做为一个很高的知识点&#xff0c;问题是&#xff0c;在ROS2的程序实验&#xff0c;需要界面支持&#xff0c;或用界面显得更加方便&#xff0c;因而专门启动该栏目专门介绍QT方法。因为体系比较庞大&#xff0c;因此&#xff0c;需要一点一点渗透学习。…

OAuth2入门

1.下载资源 演示代码&#xff1a; OAuth2-example: 演示OAuth2的认证流程https://gitee.com/lisenaq/oauth2-example克隆下载到本地&#xff1a; 导入项目&#xff1a; client 客户 authorization-server 认证服务 resource-owner 资源所有者 resource-server 资源…

【MyBatis】框架特点,ORM思想,事务管理机制

1. Mybatis概述:1.1 基础知识:SSM三大框架: Spring SpringMVC MyBatis框架其实就是对通用代码的封装, 提前写好一堆接口和类, 在做项目的时候直接引入这些常用的借口和类(引入框架), 基于这些现有的接口和类进行开发, 可以大大提高开发效率.框架一般是以jar包的形式存在的, j…

【栈】单调栈详情介绍及其运用

单调栈单调栈的概述&#xff08;Overview&#xff09;何时使用单调栈模拟单调递增栈单调栈的运用&#xff08;算法练习题&#xff09;模板【练习一、单调栈】739. 每日温度【练习二、单调栈哈希表】496. 下一个更大元素 I【练习三、单调栈循环数组】503. 下一个更大元素 II【练…

基本放大器电路- (一)

运算放大器组成的电路五花八门&#xff0c;令人眼花瞭乱&#xff0c;是模拟电路中学习的重点。在分析它的工作原理时倘没有抓住核心&#xff0c;往往令人头大。为此本人特搜罗天下运放电路之应用&#xff0c;来个“庖丁解牛”&#xff0c;希望各位从事电路板维修的同行&#xf…

记录1-两数之和

给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数&#xff0c;并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是&#xff0c;数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案…

关于图片上传和在页面显示问题

最近在工作中遇到一个关于图片上传的问题。根据之前项目的经验&#xff0c;我知道目前这个公司上传图片有两种方式&#xff0c; 一种是把图片上传到公司服务器上&#xff0c;然后把图片放在服务器上的地址存在数据库中&#xff0c;要获得图片的时候直接从库中拿地址就行了另一…

卷积神经网络CNN :1.基础知识

​卷积神经网络是一种深度学习概念&#xff0c;专为处理图像而构建。机器学习是计算机从过去的经验中学习的概念。深度学习是机器学习的高级部分。CNN 旨在寻找视觉模式。 当我们人类看到图像时&#xff0c;我们看到物体、颜色等。我们在成长过程中学习这些东西&#xff0c;但计…

3.5 异常

1.概述 异常是一些用来封装错误信息的对象 它由异常的类型、提示信息、报错的行号提示三部分组成 2.异常的继承结构 3.异常的处理方式 当程序中遇到了异常,通常有两种处理方式:捕获或者向上抛出 当一个方法抛出异常,调用位置可以不做处理继续向上抛出,也可以捕获处理异常 大…

基于NOSTR协议的“公有制”版本的Twitter,去中心化社交软件Damus用后感,一个极端走向另一个极端

最近&#xff0c;一个幽灵&#xff0c;Web3的幽灵&#xff0c;在网络游荡&#xff0c;它叫Damus&#xff0c;这玩意诠释了什么叫做病毒式营销&#xff0c;滑稽的是&#xff0c;一个Web3产品却在Web2的产品链上疯狂传销&#xff0c;各方大佬纷纷为其背书&#xff0c;到底发生了什…

OpenStack Yoga安装使用kolla-ansible

基本上是按照官网文档快速入门进行安装&#xff0c;不过还有很多地方需要换源。重点在换源这块。如果说你的网关有魔法&#xff0c;那就不用看这篇文章了&#xff0c;直接复制官网命令安装。 支持的操作系统 注意&#xff1a;不再支持 CentOS 7 作为主机操作系统。Train 版本同…

【内网安全-隧道搭建】内网穿透_Ngrok上线(美版、国版二开)

目录 一、准备 1、意义&#xff1a; 2、项目&#xff1a; 二、内网穿透 1、简介&#xff1a; 三、Ngrok&#xff08;入门上线&#xff09; 1、简述&#xff1a; 2、Ngrok入门上线&#xff08;国版二开&#xff09; 3、相关工具&#xff1a; 2、Ngrok入门上线&#xff…

2023华数杯B题社会稳定预警研究的材料支撑以及解题思路【全网独家社会稳定预警研究材料支撑】

B题社会稳定预警研究 材料支撑&#xff1a;&#xff08;动态链接&#xff0c;后期会一直不断新增支撑论文进去&#xff09; 社会稳定预警研究材料支撑合集下载 部分截图如下&#xff1a;&#xff08;还会不断更新&#xff09; 题目问题B&#xff1a;社会稳定预警研究 人类和…