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

力扣141环形链表问题|快慢指针算法详细推理,判断链表是否有环|龟兔赛跑算法

做题链接


目录

 前言:

 一、算法推导:

1.假设有环并且一定会相遇,那么一定是在环内相遇,且是快指针追上慢指针。

2.有环就一定会相遇吗?快指针是每次跳两步,有没有可能把慢指针跳过去?

3.那一定会在一圈内相遇吗?

 二、开始做题: 

1.注意题目的条件,先做特殊情况处理

2.定义快慢指针和注意判断语句

3.完整代码:

三、为什么快指针每次走两步,而不是三步或更多?

1.效率和正确性平衡:

2.两步最优:


前言:

    在环形链表问题中,使用快指针和慢指针的原因在于这种方法能够高效地检测链表是否包含环。这种方法也称为“龟兔赛跑算法”,具体来说,让快指针每次移动两步,慢指针每次移动一步,可以保证在存在环的情况下两指针最终会相遇。

 一、算法推导:

1.假设有环并且一定会相遇,那么一定是在环内相遇,且是快指针追上慢指针。

一定会在环内相遇:

设慢指针速度为v,则快指针速度为2v,

走了相同时间t时,

满指针走的路程:s=vt,则快指针为2s(2vt),

因此没有环不可能相遇,相遇的话必定在环内。

快指针追上慢指针:

慢指针不可能追上快指针,因为速度没有快指针快,永远被落在后面。

只有等快指针跑下一圈时遇上慢指针。就像我们跑800m的时候,有些跑得快的同学可以在跑第二圈的时候与有些跑得慢还在跑第一圈的同学相遇。

因此相遇时的情景一定是这样: 

2.有环就一定会相遇吗?快指针是每次跳两步,有没有可能把慢指针跳过去?

建立认知:

如图,当快指针在慢指针后面,且距离1的时候,下一回合就可以相遇。

那当快指针在慢指针后面,且距离2、3、4、5、...、n时呢?

建立认知:

如图,每走一回合,两者之间的距离会-1。

也就是说,不断的走,n-1-1-1-1-1........两者距离一定会减到1。

切入角度1:

那么就会发生如下图情况,两指针相遇。

切入角度2:

不断的走,n-1-1-1-1-1........两者距离一定会减到0。此时此刻,两指针相遇 


3.那一定会在一圈内相遇吗?

设一圈的长度为c,

入环后两指针的距离为n。则n<=c。

      每一回合n-1,最坏情况下,当n=c时,一共需要c个回合,n才为0,两个指针才能相遇。c个回合,慢指针刚好走一圈。因此,一圈内肯定会相遇。


 二、开始做题: 

1.注意题目的条件,先做特殊情况处理

 if(head==null || head.next==null){return false}


2.定义快慢指针和注意判断语句

如果代码中没有环,快指针遍历到终点时会指向空,

又因为快指针每次要连跳两格,所以要判断一下fast.next,避免空指针异常


3.完整代码:

public class Solution {public boolean hasCycle(ListNode head) {if(head==null || head.next==null){return false;}ListNode fast=head;ListNode slow=head;while(fast!=null && fast.next!=null &&slow!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){return true;}}return false;}
}


三、为什么快指针每次走两步,而不是三步或更多?

1.效率和正确性平衡

     如果快指针每次走三步或更多步,可能会跳过慢指针,使得两者在环内无法相遇,或者需要更多的时间和步骤来相遇,算法的效率和简单性会下降。

2.两步最优

      前人通过大量实际问题和理论证明,快指针每次走两步,慢指针每次走一步,既能保证在环内快速相遇,又不会跳过相遇点。

相关文章:

力扣141环形链表问题|快慢指针算法详细推理,判断链表是否有环|龟兔赛跑算法

做题链接 目录 前言&#xff1a; 一、算法推导&#xff1a; 1.假设有环并且一定会相遇&#xff0c;那么一定是在环内相遇&#xff0c;且是快指针追上慢指针。 2.有环就一定会相遇吗&#xff1f;快指针是每次跳两步&#xff0c;有没有可能把慢指针跳过去&#xff1f; 3.那一定…...

React 常见的报错及解决方法

1、Warning: Invalid hook call. Hooks can only be called inside of the body of a function component. This could happen for one of the following reasons&#xff08;无效的钩子调用。钩子只能在函数组件的内部调用。这可能是由于以下原因之一&#xff09; 原因&#x…...

更新服务器nginx 1.26.1版本

今天在官网下载了nginx1的1.26.1版本&#xff0c;使用gpt的脚本想直接覆盖安装&#xff0c;脚本如下 #!/bin/bash# 设置变量 NGINX_VERSION"1.26.1" TAR_FILE"nginx-$NGINX_VERSION.tar.gz" SRC_DIR"nginx-$NGINX_VERSION"# 检查是否存在tar包 …...

JAVA代码审计JAVA0基础学习(需要WEB基础知识)DAY2

JAVA 在 SQL执行当中 分为3种写法&#xff1a; JDBC注入分析 Mybatis注入分析 Hibernate注入分析 JDBC 模式不安全JAVA代码示例部分特征 定义了一个 sql 参数 直接让用户填入id的内容 一个最简单的SQL语句就被执行了 使用安全语句却并没有被执行 Mybatis&#xff1a; #…...

SpringBoot整合elasticsearch-java

一、依赖 系统使用的是ElasticSearch8.2.0 <dependency><groupId>co.elastic.clients</groupId><artifactId>elasticsearch-java</artifactId><version>8.1.0</version> </dependency> 二、配置 1、yml文件配置 elastics…...

网络服务与应用

一、 文件传输 FTP 1、FTP采用典型的C/S架构&#xff08;即服务器端和客户端模型&#xff09;&#xff0c;客户端与服务器端建立TCP连接之后即可实现文件的上传、下载。 2、FTP传输过程 1&#xff09;、主动模式&#xff08;POST&#xff09;&#xff1a;入站连接 2&#x…...

Git项目如何配置,如何上传至GitHub

Git项目配置并上传至GitHub的详细步骤如下&#xff1a; 一、准备工作 创建GitHub账号&#xff1a; 访问GitHub官网&#xff0c;点击“Sign up”注册新账号。填写相关信息&#xff0c;包括用户名、邮箱和密码&#xff0c;完成账号创建。安装Git客户端&#xff1a; 访问Git官网…...

Python教程(一):环境搭建及PyCharm安装

目录 引言1. Python简介1.1 编译型语言 VS 解释型语言 2. Python的独特之处3. Python应用全览4. Python版本及区别5. 环境搭建5.1 安装Python&#xff1a; 6. 开发工具&#xff08;IDE&#xff09;6.1 PyCharm安装教程6.2 永久使用教程 7. 编写第一个Hello World结语 引言 在当…...

神经网络与注意力机制的权重学习对比:公式探索

神经网络与注意力机制的权重学习对比&#xff1a;公式探索 注意力机制与神经网络权重学习的核心差异 在探讨神经网络与注意力机制的权重学习时&#xff0c;一个核心差异在于它们如何处理输入数据的权重。神经网络通常通过反向传播算法学习权重&#xff0c;而注意力机制则通过学…...

C语言------指针讲解(3)

一、字符指针 在指针中&#xff0c;我们知道有一类指针类型为字符指针char*; int main() {char ch w;char* pc &ch;*pc w;return 0; } 还有一种使用方式如下&#xff1a; 上述代码中&#xff0c;本质是把hello的首字符的地址放到了pstr中。即把一个常量字符串的首字符…...

博客建站 - 常用的公共DNS服务器

国内公共DNS服务 服务器名称首选DNS服务备用DNS服务114 DNS114.114.114.114114.114.115.115阿里 DNS223.5.5.5223.6.6.6腾讯云公共DNS119.29.29.29182.254.116.116百度公共DNS180.76.76.76110.242.68.68 国外公共DNS服务 服务器名称首选DNS服务备用DNS服务备注Google DNS8.8…...

用Redisson的RMap做一个简单的购物车示例

RMap是Redisson提供的一个高级数据结构&#xff0c;它封装了Redis中的Hash数据类型&#xff0c;提供了一个类似Java HashMap的接口。RMap非常适合在需要分布式共享的键值对集合场景中使用&#xff0c;以下是一些典型的应用场景&#xff1a; 分布式缓存&#xff1a; RMap可以用作…...

「12月·长沙」第四届机器人、自动化与智能控制国际会议(ICRAIC 2024)

随着科技的飞速发展&#xff0c;智能机器人在当今社会的重要性愈发凸显。从制造业的自动化生产线&#xff0c;到医疗领域的手术机器人&#xff0c;再到家庭生活中的智能助手&#xff0c;机器人与人工智能的融合正在改变着我们的生产和生活方式。第四届机器人、自动化与智能控制…...

传神社区|数据集合集第7期|法律NLP数据集合集

自从ChatGPT等大型语言模型&#xff08;Large Language Model, LLM&#xff09;出现以来&#xff0c;其类通用人工智能&#xff08;AGI&#xff09;能力引发了自然语言处理&#xff08;NLP&#xff09;领域的新一轮研究和应用浪潮。尤其是ChatGLM、LLaMA等普通开发者都能运行的…...

完美解决Ubuntu的MySQL临时文件夹修改调整

打开终端&#xff0c;输入以下命令 $ sudo -i # 切换root用户 $ systemctl stop mysql.service $ mkdir /home/tmp $ chown root:root /home/tmp $ chmod 1777 /home/tmp $ gedit /etc/mysql/mysql.conf.d/mysqld.cnf以上最后一条命令执行完后&#xff0c;在打开的mysqld.cnf文…...

shell基础编程

初始shell 程序 语言 编程 ---------------------------------- 语言 自然语言:汉语、英语 计算机语言:c语言、c、(java php python go shell) 编译型语言 c c java 解释型语言 php python bash ​ 编译型语言:编译型语言的首先将源代码编译生成机器语言&#xff0c;再由机…...

近期代码报错解决笔记

1.TypeError: ‘bool’ object is not callable 想print("Type of head:", type(entity_emb[head]))&#xff0c;结果报如下错误&#xff1a; 源代码&#xff1a; 因为 print 仍然被当作一个布尔值处理&#xff0c;而不是作为函数调用。这个问题的根源在于 print …...

apache设置ssl代理

<VirtualHost *:8082> ServerName localhost DocumentRoot D:\xampp\htdocs\somgl\dist #证书 SSLProtocol all -SSLv2 SSLCipherSuite DEFAULT:!EXP:!SSLv2:!DES:!IDEA:!SEED:3DES SSLEngine on SSLProxyEngine on SSLProxyVerify…...

数据库中单表的查询(select)

单表查询 所有的查找都会得到一张虚拟表 一、 最简单的查询 SELECT 123; SELECT asd; SELECT 11;二、 从表中获取数据 select 字段名,字段名 from 表名 2.1 全字段查询 SELECT sid,sname,birthday,ssex,classid FROM student; SELECT * FROM student; -- 使用*不利于s…...

Spring源码-BeanFactory类关系层级

BeanFactory 访问Spring bean容器的根接口。 这是bean容器的基本客户端视图;例如{link ListableBeanFactory}和{link org.springframework.beans.factory.config。ConfigurableBeanFactory}可用于特定目的。 这个接口是由包含许多bean定义的对象实现的&#xff0c;每个bean定义…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...