LeetCode 142题解|环形链表II的快慢指针法(含数学证明)
题目如下:

解题过程如下:
思路:快慢指针在环里一定会相遇,相遇结点到入环起始结点的距离 == 链表头结点到入环起始结点的距离(距离看从左往右的方向,也就是单链表的方向),从链表头结点和相遇结点遍历,只要结点一样,那么这个结点就是入环起始结点。
示例1、示例2为例,
示例1:相遇结点到入环起始结点的距离1 == 链表头结点到入环起始结点的距离1
示例2:相遇结点到入环起始结点的距离0 == 链表头结点到入环起始结点的距离0

完整代码如下:
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {//快慢指针ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;//快慢指针相遇if (slow == fast){//链表头结点和相遇结点开始往后遍历,结点一样,这个结点就是入环起始结点ListNode* pcur = head;while (slow != pcur){slow = slow->next;pcur = pcur->next;}return slow;}}//fast == NULL 或 fast->next == NULL,跳出循环,说明没有环return NULL;
}
试着证明:
为什么在带环链表中,链表的头结点和快慢指针相遇结点到入环起始结点的距离相等?

假设:链表的头结点到入环起始结点的距离是L,环的周长是R,若slow刚刚入环时fast已经在环里绕了n圈了(n至少为1,因为fast先进环中到M点,后又和slow在M点相遇),入环起始结点到相遇结点之间的距离是X。
慢指针进环后,快指针肯定会在慢指针走一圈之内追上慢指针。因为在快慢指针都进环之后,快慢指针之间的距离最多就是一个环的周长,快指针每追击1次,二者之间的距离就会缩小1步,所以,在慢指针移动一圈之前,快指针一定会追上慢指针。
若已经相遇,快慢指针走过的路程:
慢指针 = L + X
快指针 = L + X + nR
由于快慢指针走过的路程之间的关系2 * 慢指针 = 快指针,得出L = nR - X = (n - 1)R + R - X,式子L = (n - 1)R + R - X(n为1,2,3,4,……,n的大小取决于环的大小,环越大n越小)中,(n - 1)R表示绕(n - 1)圈,取极端情况,n = 1时,式子最终可以看成L = R - X,即slow指针从链表起始位置开始向后遍历,fast指针在相遇点开始环绕,最终一定会在入环起始结点相遇;也就是说,在带环链表中,链表的头结点和快慢指针相遇结点到入环起始结点的距离相等。
相关文章:
LeetCode 142题解|环形链表II的快慢指针法(含数学证明)
题目如下: 解题过程如下: 思路:快慢指针在环里一定会相遇,相遇结点到入环起始结点的距离 链表头结点到入环起始结点的距离(距离看从左往右的方向,也就是单链表的方向),从链表头结点…...
[图文]课程讲解片段-Fowler分析模式的剖析和实现01
解说: GJJ-004-1,分析模式高阶Fowler分析模式的剖析和实现,这个课是针对Martin Fowler的《分析模式》那本书里面的模式来讲解,对里面的模式来剖析,然后用代码来实现。 做到这一步的,我们这个是世界上独…...
Dify使用
1. 概述 官网:Dify.AI 生成式 AI 应用创新引擎 文档:欢迎使用 Dify | Dify GITHUB:langgenius/dify: Dify is an open-source LLM app development platform. Difys intuitive interface combines AI workflow, RAG pipeline, agent capabilities, model management, ob…...
解锁 DeepSeek 模型高效部署密码:蓝耘平台全解析
💖亲爱的朋友们,热烈欢迎来到 青云交的博客!能与诸位在此相逢,我倍感荣幸。在这飞速更迭的时代,我们都渴望一方心灵净土,而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识,也…...
7.PPT:“中国梦”学习实践活动【20】
目录 NO1234 NO5678 NO9\10\11 NO1234 考生文件夹下创建一个名为“PPT.pptx”的新演示文稿Word素材文档的文字:复制/挪动→“PPT.pptx”的新演示文稿(蓝色、黑色、红色) 视图→幻灯片母版→重命名:“中国梦母版1”→背景样…...
Linux系统-centos防火墙firewalld详解
Linux系统-centos7.6 防火墙firewalld详解 1 firewalld了解 CentOS 7.6默认的防火墙管理工具是firewalld,它取代了之前的iptables防火墙。firewalld属于典型的包过滤防火墙或称之为网络层防火墙,与iptables一样,都是用来管理防火墙的工具&a…...
零基础都可以本地部署Deepseek R1
文章目录 一、硬件配置需求二、详细部署步骤1. 安装 Ollama 工具2. 部署 DeepSeek-R1 模型3. API使用4. 配置图形化交互界面(可选)5. 使用与注意事项 一、硬件配置需求 不同版本的 DeepSeek-R1 模型参数量不同,对硬件资源的要求也不尽相同。…...
通过Ollama本地部署DeepSeek R1以及简单使用的教程(超详细)
本文介绍了在Windows环境下,通过Ollama来本地部署DeepSeek R1。该问包含了Ollama的下载、安装、安装目录迁移、大模型存储位置修改、下载DeepSeek以及通过Web UI来对话等相关内容。 1、🥇下载Ollama 首先我们到Ollama官网去下载安装包,此处我…...
css实现长尾箭头(夹角小于45度的)
1. 长尾夹角小于45度的箭头 代码 //h5<div class"singleArrow"></div>//css .singleArrow {width: 150px;height: 1px;position: relative;background-color: #15ff00;/* transform: rotate(-40deg); */ /* 旋转角度 */}.singleArrow::after{ // 成品-有…...
封装descriptions组件,描述,灵活
效果 1、组件1,dade-descriptions.vue <template><table><tbody><slot></slot></tbody> </table> </template><script> </script><style scoped>table {width: 100%;border-collapse: coll…...
OC-Block
关于OC中的block作为属性时,为什么要要用copy修饰 property (nonatomic, copy) void (^completionBlock)(void);很多文章包括AI都会给出类似结论 Block 默认分配在栈上,如果没有 copy,当方法退出后,Block 会被销毁。使用 copy 修…...
关于知识蒸馏的概念原理以及常见方法
1. 概念与原理 知识蒸馏的基本定义 知识蒸馏(Knowledge Distillation) 是一种将模型压缩与迁移学习结合的技术:它利用预先训练好的大模型(通常参数量大、精度高、计算开销大)指导一个更轻量(参数量小、推理速度快)的学生模型进行训练,从而在保持模型精度的同时显著减少…...
C++轻量级桌面GUI库FLTK
C轻量级桌面GUI库FLTK Screenshots - Fast Light Toolkit (FLTK) 这里写个备忘录,可以参考一下....
C++20导出模块及使用
1.模块声明 .ixx文件为导入模块文件 math_operations.ixx export module math_operations;//模块导出 //导出命名空间 export namespace math_ {//导出命名空间中函数int add(int a, int b);int sub(int a, int b);int mul(int a, int b);int div(int a, int b); } .cppm文件…...
PID 算法简介(C语言)
一、简介: PID是比例、积分、微分三个环节的组合,用来进行反馈控制。每个部分都有对应的系数,也就是Kp、Ki、Kd。PID 算法实现这三个部分的计算,然后综合起来得到控制输出。 二、PID控制器结构体: PID控制器结构体:包含PID参数(Kp, Ki, Kd);存储积分项和上一次误差;…...
Java中的继承及相关概念
在 Java 中,继承是一种允许一个类继承另一个类的特性。通过继承,子类可以获取父类的属性和方法,这有助于减少代码冗余并提高代码的可维护性。以下是关于文件内容的相关分析和知识点总结: 一、继承的核心概念 1.继承的语法 Java …...
语言月赛 202308【小粉兔做麻辣兔头】题解(AC)
》》》点我查看「视频」详解》》》 [语言月赛 202308] 小粉兔做麻辣兔头 题目描述 粉兔喜欢吃麻辣兔头,麻辣兔头的辣度分为若干级,用数字表示,数字越大,兔头越辣。为了庆祝粉兔专题赛 #1 的顺利举行,粉兔要做一些麻…...
云原生后端|实践?
云原生(Cloud Native)是一种构建和运行应用程序的方法,它充分利用云计算的优势,包括弹性、可扩展性、高可用性和自动化运维。云原生后端开发通常涉及微服务架构、容器化、持续集成/持续部署(CI/CD)、服务网…...
GrassWebProxy
GrassWebProxy第一版: using System; using System.Collections.Generic; using System.Linq; using System.Net.Sockets; using System.Net; using System.Text; using System.Threading; using System.Threading.Tasks; using System.IO; using Newtonsoft.Json;…...
6.Python函数:函数定义、函数的类型、函数参数、函数返回值、函数嵌套、局部变量、全局变量、递归函数、匿名函数
1. 函数定义 Python函数通过def关键字定义。一个函数通常包括函数名、参数列表和函数体。 def greet(name):return f"Hello, {name}!"2. 函数的类型 Python中的函数主要有以下几种类型: 普通函数:具有明确的输入参数和返回值。递归函数&am…...
OpenClaw隐私保护实践:GLM-4.7-Flash本地处理敏感数据
OpenClaw隐私保护实践:GLM-4.7-Flash本地处理敏感数据 1. 为什么选择本地化方案处理敏感数据 去年我在处理一批客户合同时遇到了一个棘手问题——合同中包含大量身份证号、银行账号等敏感信息,而团队当时使用的云端AI解析服务需要上传完整文件。虽然服…...
ARMv8开发实战:Aarch64函数调用那些坑(含AAPCS64避坑指南)
ARMv8开发实战:Aarch64函数调用那些坑(含AAPCS64避坑指南) 在嵌入式开发和系统编程领域,ARMv8架构因其出色的能效比和性能表现,已经成为移动设备、服务器甚至超级计算机的主流选择。然而,当开发者从x86平台…...
为什么很多人学 Django 会懵?因为没搞懂 MVC 和 MTV 的真正区别
很多刚接触 Django 的开发者,甚至包括不少测试工程师,在学习 Django 时都会遇到一个困惑:为什么 Django 不叫 MVC,而是 MTV?更奇怪的是:很多教程还会说:“Django 的 MTV 其实就是 MVC。”这句话…...
从SuperGlue到LoFTR:无检测器特征匹配是如何“卷”出来的?技术演进深度解读
从SuperGlue到LoFTR:无检测器特征匹配的技术革命与范式迁移 在计算机视觉领域,特征匹配一直是三维重建、SLAM、图像配准等任务的核心基础。传统方法如SIFT、ORB等基于手工设计的特征检测与描述算法,在过去二十年里主导了这一领域。然而&#…...
5步实现Switch控制器PC全功能适配:从连接到精通的设备适配指南
5步实现Switch控制器PC全功能适配:从连接到精通的设备适配指南 【免费下载链接】BetterJoy Allows the Nintendo Switch Pro Controller, Joycons and SNES controller to be used with CEMU, Citra, Dolphin, Yuzu and as generic XInput 项目地址: https://gitc…...
小型电动助力播种机【设计说明书+CAD图纸+solidworks三维+STEP+IGS】
小型电动助力播种机是针对传统播种作业效率低、劳动强度大的问题设计的农业机械装置,其核心作用在于通过电动助力系统优化播种流程,实现均匀播种与精准控制。该装置采用模块化设计理念,将动力传输、播种控制与行走机构集成于一体,…...
ArcGIS Pro模型构建器实战:从零搭建自动化地理处理工作流
1. 初识ArcGIS Pro模型构建器 第一次接触ArcGIS Pro的模型构建器时,我完全被它的可视化操作界面惊艳到了。这就像搭积木一样,不需要写一行代码,就能把复杂的地理处理流程串起来。记得当时有个项目需要批量处理上百个乡镇的耕地数据࿰…...
3步释放20GB空间:给Android用户的系统减负指南
3步释放20GB空间:给Android用户的系统减负指南 【免费下载链接】universal-android-debloater Cross-platform GUI written in Rust using ADB to debloat non-rooted android devices. Improve your privacy, the security and battery life of your device. 项目…...
Unity引擎开发过的VR大场景项目网络技术,资源处理及热更新方案的报价大概多少
根据最新的市场招标数据、行业报价案例和技术方案分析,针对VR大场景项目的网络技术、资源处理、热更新方案三大模块的报价,整理如下:一、网络技术方案报价 网络技术方案主要解决多人在线同步、远程渲染、低延迟通信等问题。方案类型技术选型报…...
s2-pro效果惊艳展示:情感化语音合成——喜悦、平静、关切语调
s2-pro效果惊艳展示:情感化语音合成——喜悦、平静、关切语调 1. 专业级语音合成新标杆 s2-pro作为Fish Audio开源的专业级语音合成模型镜像,正在重新定义文本转语音的技术边界。不同于传统单调的语音合成,这款工具能够精准捕捉并复现人类语…...
