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

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&#xff0c;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作为属性时&#xff0c;为什么要要用copy修饰 property (nonatomic, copy) void (^completionBlock)(void);很多文章包括AI都会给出类似结论 Block 默认分配在栈上&#xff0c;如果没有 copy&#xff0c;当方法退出后&#xff0c;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 中&#xff0c;继承是一种允许一个类继承另一个类的特性。通过继承&#xff0c;子类可以获取父类的属性和方法&#xff0c;这有助于减少代码冗余并提高代码的可维护性。以下是关于文件内容的相关分析和知识点总结&#xff1a; 一、继承的核心概念 1.继承的语法 Java …...

语言月赛 202308【小粉兔做麻辣兔头】题解(AC)

》》》点我查看「视频」详解》》》 [语言月赛 202308] 小粉兔做麻辣兔头 题目描述 粉兔喜欢吃麻辣兔头&#xff0c;麻辣兔头的辣度分为若干级&#xff0c;用数字表示&#xff0c;数字越大&#xff0c;兔头越辣。为了庆祝粉兔专题赛 #1 的顺利举行&#xff0c;粉兔要做一些麻…...

云原生后端|实践?

云原生&#xff08;Cloud Native&#xff09;是一种构建和运行应用程序的方法&#xff0c;它充分利用云计算的优势&#xff0c;包括弹性、可扩展性、高可用性和自动化运维。云原生后端开发通常涉及微服务架构、容器化、持续集成/持续部署&#xff08;CI/CD&#xff09;、服务网…...

GrassWebProxy

GrassWebProxy第一版&#xff1a; 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中的函数主要有以下几种类型&#xff1a; 普通函数&#xff1a;具有明确的输入参数和返回值。递归函数&am…...

51单片机驱动DS1302:从时序解析到精准电子钟实战

1. 初识DS1302&#xff1a;你的第一个实时时钟芯片 第一次接触DS1302时&#xff0c;我盯着这个只有8个引脚的小芯片看了半天——这么小的东西真的能准确记录时间吗&#xff1f;事实证明它不仅做得到&#xff0c;而且做得很好。DS1302是Dallas公司推出的一款经典实时时钟芯片&am…...

解决QGroundControl或华科尔地面站因QT版本冲突导致的启动失败问题

1. 当QGroundControl或华科尔地面站打不开时该怎么办 遇到QGroundControl或华科尔地面站安装后无法启动的问题&#xff0c;很多用户第一反应是软件安装包损坏了。但实际上&#xff0c;这很可能是由于QT框架版本冲突导致的。QT是一个跨平台的C图形用户界面应用程序开发框架&…...

从订餐流程到并发编程:Petri网中的‘库所’与‘变迁’到底在模拟什么?

从订餐流程到并发编程&#xff1a;Petri网中的‘库所’与‘变迁’到底在模拟什么&#xff1f; 想象一下&#xff0c;你正在用手机订外卖&#xff1a;选择菜品、下单支付、等待制作、骑手配送——这个看似简单的流程背后&#xff0c;隐藏着一个精妙的系统状态转换模型。这正是Pe…...

OpenClaw多模态飞书助手:Qwen3-VL:30B实战指南

OpenClaw多模态飞书助手&#xff1a;Qwen3-VL:30B实战指南 1. 为什么我们需要多模态飞书助手&#xff1f; 去年夏天&#xff0c;我负责一个跨部门协作项目时&#xff0c;每天要处理上百条飞书消息和几十份文档。最头疼的是同事发来的截图——有时是数据图表&#xff0c;有时是…...

28:L构建AI Agent安全:蓝队的智能代理防御

作者&#xff1a; HOS(安全风信子) 日期&#xff1a; 2026-03-19 主要来源平台&#xff1a; GitHub 摘要&#xff1a; AI Agent的发展为安全防御带来了新的可能性&#xff0c;但也带来了新的安全挑战。基拉等对手可能利用AI Agent进行攻击。L深入研究AI Agent安全技术&#xff…...

让ai成为你的vue开发搭档,用快马智能优化代码性能与结构

让AI成为你的Vue开发搭档&#xff0c;用快马智能优化代码性能与结构 最近在开发一个Vue3项目时&#xff0c;遇到了几个性能瓶颈问题。作为一个前端开发者&#xff0c;性能优化是绕不开的话题。幸运的是&#xff0c;借助AI辅助开发工具&#xff0c;这些问题都能得到更高效的解决…...

IP5306电源芯片的‘怪脾气’:实测开机半分钟就休眠?手把手教你两个硬件调试技巧

IP5306电源芯片实战调试&#xff1a;破解自动休眠难题的硬件级方案 实验室里&#xff0c;示波器屏幕上那条本该稳定的电压线突然跌落至零&#xff0c;系统再次陷入休眠——这已经是今天第七次重现IP5306芯片的"怪脾气"。作为一款广泛应用于移动电源的高集成度SOC&…...

【概率统计】从直方图到核密度估计:数据分布可视化的进阶之路

1. 直方图&#xff1a;数据可视化的第一课 第一次接触数据分布可视化时&#xff0c;大多数人都是从直方图开始的。记得我刚学数据分析时&#xff0c;导师扔给我一组销售数据说&#xff1a;"先画个直方图看看分布情况。"当时我盯着matplotlib的hist函数参数一脸茫然—…...

用LVGL玩转嵌入式UI:5个实战控件代码详解(按钮/滑块/图片/标签/开关)

LVGL嵌入式UI开发实战&#xff1a;五大核心控件深度解析与代码优化 在资源受限的嵌入式设备上实现流畅美观的用户界面&#xff0c;一直是开发者面临的挑战。LVGL&#xff08;Light and Versatile Graphics Library&#xff09;作为一款轻量级开源图形库&#xff0c;凭借其丰富的…...

YOLOv8目标检测新玩法:用VMamba替换C2f模块,我在DDSM医疗数据集上mAP涨到了0.724

YOLOv8与VMamba融合&#xff1a;医疗影像目标检测的突破实践 在医疗影像分析领域&#xff0c;目标检测技术正经历着从传统卷积神经网络到新型架构的转变。最近&#xff0c;我们将YOLOv8模型中的C2f模块替换为VMamba模块&#xff0c;在DDSM乳腺X光数据集上取得了mAP 0.724的显著…...