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

力扣刷题TOP101：6.BM7 链表中环的入口结点

news 来源：原创 2025/5/16 11:56:22

目录：

目的

思路

复杂度

记忆秘诀

python代码

`目的`

{1,2},{3,4,5}, 3 是环入口。

思路

这个任务是找到带环链表的环入口。可以看作是上一题龟兔赛跑（Floyd 判圈算法）的延续版：乌龟愤愤不平地举报兔子跑得太快，偷偷回头朝自己炫耀得瑟，还说在环口撒了尿标记。裁判接到举报，准备调取“监控记录”，验证兔子是否偷偷回头，并定位撒标记的位置（环入口）。

裁判开始审理过程：

参赛选手：
- 乌龟（慢指针slow）： 每次只走一步，慢悠悠的。slow = head
- 兔子（快指针fast）： 从同样的起点出发，每次跳两步，永远快人一步。fast = head
- 观察双方起点位置，从同样的起点出发

比赛规则：

只要兔子还没跑出链表（fast != None 且 fast.next != None），比赛继续。

为什么检查两个条件？
fast： 如果 fast == None，说明兔子已经跑到了链表的尽头，没有环。
fast.next： 是兔子跳两步时需要访问的下一个节点。fast.next == None，说明兔子已经没有“下一步”可以跳，也意味着链表没有环。

比赛开始：

乌龟稳步前进：走一步，代表慢速slow = slow.next。
兔子飞速跳跃：跳两步，代表快速移动fast = fast.next.next。
是否龟兔同镜（相遇点）：如果他们在一个镜头中出现（slow == fast），裁判记录兔子回头了，继续调查。如果没有出现（环），直接结束，乌龟举报无效，返回 None。
为什么一定会相遇？
- 如果链表是闭环，兔子因为步伐更快，最终会在环内兜圈，追上乌龟。

寻找兔子撒尿点（环口）：

裁判让乌龟回到起点：

乌龟回到起点，准备和兔子一同慢跑：slow = pHead。

兔子在相遇点陪乌龟慢慢走：

这次双方步伐一致，每次只走一步：
slow = slow.next
fast = fast.next

两者最终相遇（具体可查看下面详细的数学推导）：

当两者再次相遇时slow == fast，位置就是环的入口节点，也就是兔子撒尿炫耀的地方。

举报成功：

裁判员找到了兔子撒尿标记的地方（环的入口节点）并提交结果return slow，乌龟举报成功，取消兔子的比赛成绩。

复杂度

时间复杂度：O(n）
- 每次兔子和乌龟各走一段路，总路程不会超过链表长度的两倍。
空间复杂度：O(1)
- 只用了两只小动物（两个指针变量），省吃俭用，不多花内存。

记忆秘诀

乌龟走一步，兔子跳两步。
链表有环，相遇无误。
链表无环，兔子先停步。
环点未锁住，乌龟再起步
兔子陪跑步，入口终汇聚

补充：数学推导

设链表为一个带环的结构，其中：

a：链表头节点到环入口的距离（环前的直线段）。
b：环入口到相遇点的距离（在环中的第一部分）。
c：相遇点到环入口的剩余距离（环中的第二部分）。
n：兔子绕环的圈数。
兔子的距离是乌龟的两倍：
2(a+b)=a+b+n(b+c)
- 兔子每次跳两步，乌龟每次走一步，因此兔子走的距离总是乌龟的两倍。
化简公式：消去公共项 a+b，得到：a=c+(n−1)(b+c)
- 乌龟的距离：当乌龟从起点走 a距离时，会刚好到达环的入口。
- 兔子的距离：兔子从相遇点出发，绕过 c距离后也会到达环的入口。
- 同步抵达环入口：因为 n−1表示兔子可能多绕了若干圈，但最终兔子和乌龟都会同时抵达环入口。
找到环入口的核心原因：
- 相遇后，将乌龟放回起点，兔子留在相遇点。
- 两者按相同速度行进（每次一步），兔子绕过剩余的 c 距离时，乌龟正好走完 a，两者在环入口相遇。

python代码

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:def EntryNodeOfLoop(self, pHead: ListNode) -> ListNode:# 快慢指针法：检测环slow = pHeadfast = pHead# 检测是否有环while fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:  # 快慢指针相遇，说明有环breakelse:return None  # 如果没有环，返回 None# 重新开始寻找环的入口slow = pHead  # 慢指针重新指向头节点while slow != fast:slow = slow.nextfast = fast.next  # 两个指针每次都走一步# 相遇时即为环的入口return slow

* 欢迎大家探讨新思路，能够更好的理解和记忆

力扣刷题TOP101：6.BM7 链表中环的入口结点

目录： 目的思路复杂度记忆秘诀 python代码目的 {1,2},{3,4,5}, 3 是环入口。思路这个任务是找到带环链表的环入口。可以看作是上一题龟兔赛跑（Floyd 判圈算法）的延续版：乌龟愤愤不平地举报兔子跑得太快，偷偷…...

编程日记 2025/5/16 11:56:22

智慧防汛平台在城市生命线安全建设中的应用

随着城市化进程的加快，城市基础设施的复杂性和互联性不断增强，城市生命线的安全管理面临前所未有的挑战。智慧防汛平台作为城市生命线安全建设的重要组成部分，通过现代信息技术提升城市防汛应急管理的智能化水平，保障城市安全。 …...

编程日记 2025/5/16 11:48:03

高德应用OceanBase云数据库的升级选型与迁移干货

业务背景高德，DAU已在亿级，时时刻刻都持续不断地产生着庞大的数据。随着数据量的迅猛增长，对现有的业务数据存储能力构成日益严峻的挑战。以我所在部门中的某一大型服务为例，其存储在XDB中的数据量往往达到数百TB之巨&#xf…...

编程日记 2025/5/4 8:09:16

Flink cdc同步增量数据timestamp字段相差八小时（分析｜解决）不是粘贴复制的！

问题我使用flink cdc同步mysql到mysql遇到了timestamp字段缺少八小时的问题。很少无语，flink ,cdc,debezium时区都设置了，没有任何效果！ 分析问题出现在mysql binlog身上！！！ 因为默认mysql会使用UTC来…...

编程日记 2025/5/15 20:45:24

用shell脚本写一个通用的监听程序异常并重启脚本

进来服务器的程序php-fpm时常在并发下时常挂掉，而且时常在凌晨2点以后，通过排查是因为php配置需要调整并发，同时，为了不影响我休息（以前老师说：能用机器和程序解决问题的坚决不用人去操作，这样才…...

编程日记 2025/5/5 20:02:48

使用 Go 语言中的 Context 取消协程执行

使用 Go 语言中的 Context 取消协程执行在 Go 语言中，协程（goroutine）是一种轻量级的线程，非常适合处理并发任务。然而，如何优雅地取消正在运行的协程是一个常见的问题。本文将通过一个具体的例子来展示如何使用 con…...

编程日记 2025/5/15 7:00:10

使用经典的Java，还是拥抱新兴的Rust？

在当代互联网时代的企业级开发中，技术栈的选择往往牵动着每个团队的神经。随着Rust语言的崛起，许多开发团队开始重新思考：是继续坚持使用经典的Java，还是拥抱新兴的Rust？这个问题背后，折射出的是对技术演进…...

编程日记 2025/5/6 8:07:35

《算法导论》英文版前言To the teacher第3段研习录：题海战术有没有？

【英文版】 We have included 957 exercises and 158 problems. Each section ends with exercises, and each chapter ends with problems. The exercises are generally short questions that test basic mastery of the material. Some are simple self-check thought exer…...

编程日记 2025/5/16 11:33:30

XELA - uSkin 三轴触觉传感器：为机器人赋予敏锐触感

XELA Robotics 的 uSkin 触觉传感器以其创新性在机器人技术中备受关注。它凭借高密度设计和三轴力测量能力，大幅提升了机器人的触觉感知能力，这种技术不但增强了机器人的智能化和柔性，还为不同行业的应用创造了广泛的可能性。其中在机器人灵巧…...

编程日记 2025/5/14 21:32:24

k8s常用命令总结

以下是 Kubernetes 所有常用命令的详细总结，涵盖了 kubectl 的各个方面，包括基本操作、资源管理、调试、监控等。每个命令都附有简要说明和示例。 1. 基本命令查看 Kubernetes 版本 kubectl version 查看集群信息 kubectl cluster-info 查看当前上…...

编程日记 2025/5/14 15:09:39

即时通讯| IM+RTC在AI技术加持下的社交体验

即时通讯作为互联网的重要应用之一，见证了中国互联网30年发展的辉煌历程。它从最初的文字交流，发展到如今的语音、视频通话，甚至是虚拟现实社交，已经渗透到生活的社交、娱乐、商务等方方面面，成为现代社会不可或缺的一…...

编程日记 2025/5/9 10:51:40

评估人工智能生成答案准确性

目录评估人工智能生成答案准确性评估人工智能生成答案准确性在评估人工智能（AI）系统生成的答案准确性时，我们主要关注两个方面：事实相似性和语义相似性。这两个方面的加权平均分数被用来衡量系统回答的准确性。事实相似性：事实相似性通过F1分数来计算。F1分数是精确…...

编程日记 2025/5/4 13:38:28

scala的守卫语句格式

import scala.io.StdIn object test49{//从控制台读入一个数字a,使用（StdIn.readInt）//如果a>0并且a<3,打印[0-3]//如果a>4并且a<8,打印[4-8]//否则:打印未匹配 // def main(args: Array[String]): Unit { // val aStdIn.readInt()//等…...

编程日记 2025/5/13 11:37:46

结构型模式-组合模式

组合模式（Composite Pattern）是一种结构型设计模式，它通过将对象组合成树形结构来表示“部分-整体”的层次结构，从而使客户端对单个对象和组合对象的使用具有一致性。适用场景需要表示对象的层次结构：如文件系统、组…...

编程日记 2025/5/11 15:26:28

（超详细图文）PLSQL Developer 配置连接远程 Oracle 服务

1、下载配置文件 （超详细图文详情）Navicat 配置连接 Oracle-CSDN博客将下载的文件解压到单独文件夹，如：D:\App\App_Java\Oracle\instantclient-basic-windows.x64-19.25.0.0.0dbru 2、配置打开 PLSQL Developer，登…...

编程日记 2025/5/15 9:07:01

【AI系统】昇腾 AI 架构介绍

昇腾 AI 架构介绍昇腾计算的基础软硬件是产业的核⼼，也是 AI 计算能⼒的来源。华为，作为昇腾计算产业⽣态的⼀员，是基础软硬件系统的核⼼贡献者。昇腾计算软硬件包括硬件系统、基础软件和应⽤使能等。而本书介绍的 AI 系统整体架构&#…...

编程日记 2025/5/12 10:29:47

D83【python 接口自动化学习】- pytest基础用法

day83 pytest测试用例执行顺序学习日期：20241129 学习目标：http定义及实战 -- pytest测试用例执行顺序学习笔记： 测试用例执行顺序默认执行顺序使用pytest-ordering自定义顺序 pytestrequests练习 import requestsdef test_mobile()…...

编程日记 2025/5/15 9:22:02

浅谈C#库之Memcached

一、Memcached库介绍 Memcached是一个开源的高性能分布式内存缓存系统，它通过将数据存储在内存中来加速动态Web应用。以下是Memcached的一些关键特点： 1、高性能：Memcached使用内存进行数据存储，访问速度极快。 2、分布式&…...

编程日记 2025/5/14 5:44:27

基于Matlab的图像去噪算法仿真

中值滤波的仿真本节选用中值滤波法对含有高斯噪声和椒盐噪声的图像进行去噪，并用Matlab软件仿真。 （1）给图像加入均值为0，方差为0.02的高斯噪声，分别选择33模板、55模板和77模板进行去噪 Matlab部分代码&#xff1…...

编程日记 2025/5/11 21:18:34

YOLOv9改进，YOLOv9引入CAS-ViT（卷积加自注意力视觉变压器）中AdditiveBlock模块，二次创新RepNCSPELAN4结构

摘要 CAS-ViT 是一种为高效移动应用设计的视觉Transformer。模型通过结合卷积操作与加性自注意机制，在保持高性能的同时显著减少计算开销，适合资源受限的设备如手机。其核心组件 AdditiveBlock 通过多维度信息交互和简化的加性相似函数，实现了高效的上下文信息整合，避免了…...

编程日记 2025/5/9 0:59:50

Ubuntu 关机命令

在 Ubuntu 系统中，有几种方法可以关机。以下是常用的关机命令及其说明： 1. 使用 shutdown 命令 shutdown 命令是最常用和最灵活的关机方式。它可以设置定时关机，并且可以发送警告消息给所有登录用户。立即关机 sudo shutdown now定时关机…...

编程日记 2025/5/11 9:06:20

使用Gradle编译前端的项目

使用Gradle编译前端的项目前言项目结构根项目（parent-project）的 settings.gradle.kts后端项目（backend）的 build.gradle.kts前端项目（frontend）的 build.gradle.kts打包bootJar 前言最近的项目都是使用…...

编程日记 2025/5/16 6:27:30

React进阶面试题目（三）

如何在 React 中实现滚动动画？ 在 React 中实现滚动动画可以通过多种方式实现，以下是一个基本的实现步骤： 构建组件：首先构建需要展示滚动动画的组件，例如一个 About 组件，它包含一些文本或元素。监听滚动…...

编程日记 2025/5/16 11:28:39

每日计划-1129

1. 完成 200. 岛屿数量 class Solution { private:void dfs(vector<vector<char>>& grid,int r,int c){int nrgrid.size();int ncgrid[0].size();grid[r][c]0;if (r - 1 > 0 && grid[r-1][c] 1) dfs(grid, r - 1, c);if (r 1 < nr && …...

编程日记 2025/5/12 17:42:20

杭州网世一站式网络解决方案,助力安邦护卫网络升级改造

随着信息技术的不断进步，浙江台州安邦护卫有限公司现有的网络设备已无法满足其日益增长的业务需求。网络性能瓶颈、安全隐患和管理复杂性等问题逐渐凸显，严重影响了企业的运营效率和服务质量。为了解决这些问题，浙江台州安邦护卫有限公司决定…...

编程日记 2025/5/14 2:11:29

vue3.0 根据富文本html页面生成压缩包（含视频在线地址、图片在线地址、前端截图、前端文档）

vue3.0生成压缩包（含在线地址、前端截图、前端文档） 需求描述效果开始下载插件包基本代码构造点击下载按钮1.截图content元素，并转化为pdfcanvas putImageData、getImageDatagetImageData 获取指定矩形区域的像素信息putImageData 将这些数据…...

编程日记 2025/5/12 18:04:05

从0开始学PHP面向对象内容之常用设计模式（享元）

二、结构型设计模式 7、享元模式（Flyweight Pattern） 这里是引用享元模式（Flyweight Pattern） 是一种结构型设计模式，旨在通过共享对象来减少内存使用，尤其适用于大量相似对象的场景。通过共享和重用对象的…...

编程日记 2025/5/13 3:10:59

Idea 2024.3 突然出现点击run 运行没有反应，且没有任何提示。

写这篇文章的目的是为了提供一个新的解决思路，因为存在同病不同原因。如果你进行了1. 检查运行配置 (Run Configuration) 2. 清理和重建项目 3. 清除缓存并重启 IDEA 4.排除kotlin 5.重装idea等等操作之后仍然没有解决，可以试着按一下步骤进行解决。检…...

编程日记 2025/5/14 8:47:32

拥抱 OpenTelemetry：阿里云 Java Agent 演进实践

作者：陈承背景在 2018 年的 2 月，ARMS Java Agent 的第一个版本正式发布，为用户提供无侵入的的可观测数据采集服务。6 年后的今天，随着软件技术的迅猛发展、业务场景的逐渐丰富、用户规模的快速增长，我们逐渐发现过…...

编程日记 2025/5/13 20:44:07

【Linux】开发工具

这篇文章主要涉及sudo指令进行提权的方法，gcc/g的使用并且提及了一些make、makefile sudo指令在前几篇文章中，我们先后了解了对于不同的角色来说，可以进行不同的操作，而对于新建的普通用户是不能进行权限提升的，这是…...

编程日记 2025/5/13 15:14:17

网络通信基础：TCP/IP、UDP、三次握手、Socket与HTTP协议详解

在网络通信的世界中，TCP/IP、UDP、三次握手、Socket和HTTP协议是不可或缺的基本概念。它们构成了网络通信的基石，对于理解网络编程和设计网络应用程序至关重要。本文将详细介绍这些概念，帮助读者更好地理解网络通信的原理。首先&#xff0c…...

编程日记 2025/5/16 11:22:37

（Python）前缀和

前缀和： 前缀和预先计算并存储一系列连续元素的总和，是一种优化技巧，提高算法效率。记录一个数组中各下标位置之前的所有元素的总和，本文对应下标的总和中不含对应下标元素本身。若有需要也可以对应下标记录的总和包含下标本身元…...

编程日记 2025/5/14 3:28:52

【Linux】-操作系统

🔑🔑博客主页：阿客不是客 🍓🍓系列专栏：深入代码世界，了解掌握 Linux 欢迎来到泊舟小课堂 😘博客制作不易欢迎各位👍点赞⭐收藏➕关注一、冯•诺依曼架构&#xff…...

编程日记 2025/5/6 17:18:13

shell echo双引号和单引号区别

echo双引号"" var1"a" var2"b" echo -e "$var1\t$var2"输出： 使用双引号 "" 时，变量会被正确解析。 echo单引号‘’ var1"a" var2"b" echo -e $var1\t$var2输出： …...

编程日记 2025/5/7 23:28:31

嵌入式QT学习第3天：UI设计器的简单使用

Linux版本号4.1.15 芯片I.MX6ULL 大叔学Linux 品人间百味思文短情长 Qt Creator 里自带的 Qt Designer，使用 Qt Designer 比较方便的构造 UI 界面。在 UI 文件添加一个按钮左边找到 Push Button，然后拖拽到中…...

编程日记 2025/5/13 6:16:02

Nuxt.js 应用中的 render：response 事件钩子

title: Nuxt.js 应用中的 render：response 事件钩子 date: 2024/11/29 updated: 2024/11/29 author: cmdragon excerpt: render:response 是一个在 Nuxt.js 中与服务器端渲染（SSR）相关的钩子，它会在请求的响应发送之前被调用。这个钩子的目的是让开发者可以在响应发送之…...

编程日记 2025/5/12 15:13:59

Node报错：npm error code ETIMEDOUT

1、报错详细信息 npm error code ETIMEDOUT npm error syscall connect npm error errno ETIMEDOUT npm error network request to https://registry.npmjs.org/express failed, reason: connect ETIMEDOUT 104.16.1.35:443 npm error network This is a problem related to ne…...

编程日记 2025/5/12 6:11:37

目的

思路

复杂度

记忆秘诀

python代码

相关文章：

`目的`