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

LeetCode hot 100—环形链表 II

题目

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。

分析

哈希表法

遍历链表中的每个节点并记录下来。一旦遇到了此前遍历过的节点,就可以判定链表中存在环,直接返回该节点。

时间复杂度:O(n),n为链表中节点的数目

空间复杂度:O(n)

class Solution {
public:ListNode *detectCycle(ListNode *head) {// 使用哈希集合来存储已经访问过的节点std::unordered_set<ListNode*> visited;// 遍历链表while (head != nullptr) {// 检查当前节点是否已经在哈希集合中if (visited.count(head)) {// 如果存在,说明找到了环的入口节点,返回该节点return head;}// 将当前节点插入到哈希集合中visited.insert(head);// 移动到下一个节点head = head->next;}// 如果遍历完整个链表都没有找到环,返回 nullptrreturn nullptr;}
};

快慢指针法

判断是否有环:首先使用快慢指针判断链表中是否存在环。slow 指针每次移动一步,fast 指针每次移动两步,如果它们相遇,则说明链表中存在环。

寻找环的入口:当快慢指针相遇后,将 slow 指针重新指向链表头节点,然后 slow 和 fast 指针以相同的速度(每次移动一步)继续移动,它们再次相遇的节点就是环的入口节点。

数学推导

设链表的头节点为 head,链表中环的入口节点为 entry,从链表头到环入口的节点数为 a,从环入口到快慢指针相遇点的节点数为 b,从快慢指针相遇点再到环入口的节点数为 c,则环的长度为 b + c

慢指针 slow 每次移动一步,快指针 fast 每次移动两步。当快慢指针相遇时,假设慢指针移动了 a + b 步,快指针移动了 y 步。因为快指针速度是慢指针的两倍,所以 y = 2(a+b)

又因为快指针比慢指针多走了若干圈环,设快指针在环里走了 n 圈(n 为正整数),则有 y = a + n(b + c) + b。将 y = 2(a+b) 代入 y = a + n(b + c) + b 可得:a = c + (n - 1)(b + c)

于是从相遇点到入环点的距离加上 n−1 圈的环长,恰好等于从链表头部到入环点的距离。即当 slow 和 fast 再次相遇时,相遇的节点就是环的入口节点

时间复杂度:O(n),n为链表中节点的数目

空间复杂度:O(1)

class Solution {
public:ListNode *detectCycle(ListNode *head) {// 如果链表为空或者只有一个节点,肯定不存在环,返回 nullptrif (head == nullptr || head->next == nullptr) {return nullptr;}// 定义快慢指针ListNode* slow = head;ListNode* fast = head;// 标记是否有环bool hasCycle = false;// 移动快慢指针,快指针每次移动两步,慢指针每次移动一步while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;// 如果快慢指针相遇,说明存在环if (slow == fast) {hasCycle = true;break;}}// 如果没有环,返回 nullptrif (!hasCycle) {return nullptr;}// 让慢指针回到头节点slow = head;// 快慢指针以相同速度移动,再次相遇的节点就是环的入口节点while (slow != fast) {slow = slow->next;fast = fast->next;}return slow;}
};

相关文章:

LeetCode hot 100—环形链表 II

题目 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内部…...

【AI】【Unity】关于Unity接入DeepseekAPI遇到的坑

前言 由于deepseek网页端在白天日常抽风&#xff0c;无法正常的使用&#xff0c;所以调用API就成了目前最好的选择&#xff0c;尤其是Deepseek的API价格低得可怕&#xff0c;这不是和白送的一样吗&#xff01;然后使用过很多本地部署接入API的方式&#xff0c;例如Chatbox、Pa…...

计算机视觉算法实战——医学影像分割(主页有源码)

✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ ​ ​​​ 1. 领域简介✨✨ 医学影像分割是计算机视觉在医疗领域的重要应用&#xff0c;旨在从CT、MRI、X光等医学图像中精确分割出目标区域&…...

51单片机——存储类型

主要内容&#xff1a;区分data,bdata,idata,pdata,xdata,code 8051系列单片机存储器结构的特点&#xff1a;ROM和RAM独立编址 8051系列单片机将程序存储器&#xff08;ROM&#xff09;和数据存储器&#xff08;RAM&#xff09;分开&#xff0c;并有各自的寻址机构和寻址方式。…...

python19-if和match的美

课程&#xff1a;B站大学 记录python学习&#xff0c;直到学会基本的爬虫&#xff0c;使用python搭建接口自动化测试就算学会了&#xff0c;在进阶webui自动化&#xff0c;app自动化 分支语句那些事儿 if 条件判断if...else 判断语句if...elif...else 多重条件分支嵌套也能在 e…...

期权有哪些用处?期权和期货比优势在哪?

期权如同金融市场的“瑞士军刀”&#xff0c;既能防御风险&#xff0c;又能主动出击。相较于期货的“刚性对决”&#xff0c;期权更像“柔性博弈”——通过策略组合在不确定性中捕捉确定性收益。 期权有哪些用处&#xff1f; 期权的核心价值在于其非对称性——买方风险有限&am…...

【html期末作业网页设计】

html期末作业网页设计 作者有话说项目功能介绍 网站结构完整代码网站样图 作者有话说 目前&#xff0c;我们的项目已经搭建了各页面的基本框架&#xff0c;但内容填充还不完善&#xff0c;各页面之间的跳转逻辑也还需要进一步优化。 我们深知&#xff0c;一个好的项目需要不断…...

ComfyUI AnimeDiff动画参数总结

ComfyUI AnimeDiff动画参数总结 一、动画生成核心参数 参数名称建议值/范围作用说明备注步数&#xff08;Steps&#xff09;15-25控制AI计算迭代次数&#xff0c;越高细节越精细&#xff0c;但耗时更长推荐20步&#xff0c;显存不足可降至15步CFG值7.0-8.5提示词对画面的控制…...

基于Three.js的多视图3D Tiles同步可视化技术解析

文章目录 基于Three.js的多视图3D Tiles同步可视化技术解析一、技术背景与价值二、核心实现原理2.1 视口分割算法2.2 视角同步机制三、关键代码解析3.1 渲染管线优化3.2 3D Tiles加载四、交互系统实现4.1 多视图事件分发4.2 射线拾取优化五、性能优化方案5.1 渲染性能指标5.2 W…...

7、什么是死锁,如何避免死锁?【高频】

&#xff08;1&#xff09;什么是死锁&#xff1a; 死锁 是指在两个或多个进程的执行时&#xff0c;每个进程都持有资源&#xff0c;并都在等待其他进程 释放 它所需的资源&#xff0c;如果此时所有的进程一直占有资源而不释放&#xff0c;就导致了死锁。 死锁只有同时满足 四…...

自动化学习-使用git进行版本管理

目录 一、为什么要学习git 二、git是什么 三、git如何使用 1、git的下载安装和配置 2、git常用的命令 3、gitee远程仓库的使用 &#xff08;1&#xff09;注册 &#xff08;2&#xff09;创建仓库 &#xff08;3&#xff09;配置公钥&#xff08;建立电脑和git…...

前端大文件上传

一、切片上传技术原理 切片上传是把大文件分割成多个较小的切片&#xff0c;分别上传这些切片&#xff0c;最后在服务器端将它们合并成完整文件。这种方式能有效应对网络不稳定导致的上传失败问题&#xff0c;还可利用多线程并行上传&#xff0c;提升上传效率。 二、前端实现…...

【网络】实现电脑与笔记本电脑之间的直接网络连接

要实现电脑与笔记本电脑之间的直接网络连接&#xff0c;可以通过有线或无线两种方式。以下是详细的步骤指南&#xff1a; 一、有线直连&#xff08;通过网线&#xff09; 1. 准备工具 网线&#xff1a;使用交叉网线&#xff08;适用于旧设备&#xff09;或普通直连网线&#…...

“深入浅出”系列之音视频开发:(12)使用FFmpeg实现倍速播放:技术细节与优化思路

一、前言 在音视频处理领域&#xff0c;倍速播放是一个常见的需求&#xff0c;尤其是在视频播放器、在线教育平台等场景中&#xff0c;用户常常需要以不同的速度播放视频内容。然而&#xff0c;实现一个高质量的倍速播放功能并不容易&#xff0c;尤其是在处理音频时&#xff0…...

qt作业day2

1&#xff1a;在注册登录的练习里面&#xff0c;追加一个QListWidget 项目列表 要求&#xff1a;点击注册之后&#xff0c;将账号显示到 listWidget上面去 以及&#xff0c;在listWidget中双击某个账号的时候&#xff0c;将该账号删除 .h #ifndef WIDGET_H #define WIDGET_H …...

Qt:day1

一、作业 写1个Widget窗口&#xff0c;窗口里面放1个按钮&#xff0c;按钮随便叫什么&#xff1b; 创建2个Widget对象&#xff1a; Widget w1, w2; w1.show(); w2不管&#xff1b; 要求&#xff1a; 点击 w1.btn&#xff0c;w1隐藏&#xff0c;w2显示&#xff1b; 点击 w2.btn&…...

基于微信小程序的停车场管理系统的设计与实现

第1章 绪论 1.1 课题背景 随着移动互联形式的不断发展&#xff0c;各行各业都在摸索移动互联对本行业的改变&#xff0c;不断的尝试开发出适合于本行业或者本公司的APP。但是这样一来用户的手机上就需要安装各种软件&#xff0c;但是APP作为一个只为某个公司服务的一个软件&a…...

详细Linux基础知识(不断完善)

终端类型分类 1. 物理终端 直接连接到计算机的硬件设备2. 虚拟终端 通过快捷键切换的文本模式界面: Ctrl + Alt + F1 # 登录窗口 Ctrl + Alt + F2 # 当前图形界面 Ctrl + Alt + F3 # 虚拟命令终端 Ctrl + Alt + F4-F6 # 备用虚拟终端3. 图形终端 模拟终端:图形环境中的…...

类和对象-继承-C++

1.定义 面向对象的三大特征之一&#xff0c;为了减少重复的代码 2.语法 class 子类 &#xff1a;继承方式 父类 &#xff08;子类也叫派生类&#xff0c;父类也称为基类&#xff09; 例&#xff1a;class age&#xff1a;public person&#xff1b; #include<iostrea…...

初阶数据结构(C语言实现)——3顺序表和链表(1)

目录 【本节目标】1. 线性表2.顺序表2.1概念及结构2.2 接口实现2.2.0 动态顺序表2.2.1 顺序表初始化SLInit&#xff08;&#xff09;2.2.2 销毁和打印2.2.3 尾插SLPushBack&#xff08;&#xff09;2.2.4 尾删SLPopBack&#xff08;&#xff09;2.2.5 头插2.2.6 头删2.2.7 插入…...

nuxt常用组件库html-validator、@nuxtjs/i18n、@nuxt/image、@unocss/nuxt使用解析

html-validator 主要用于自动验证nuxt服务器呈现的HTML(SSR和SSG)&#xff0c;以检测可能导致水合错误的HTML常见问题&#xff0c;有助于减少水合错误&#xff0c;检测常见的可访问性错误。 安装 npx nuxilatest module add html-validator配置 若自动更新nuxt.config.ts配置文…...

4G工业路由器在公交充电桩中的应用与优势

随着电动公交车的普及&#xff0c;公交充电桩的稳定运行和高效管理是交通营运部门最关心的问题。4G工业路由器凭借其卓越的数据采集和通讯能力&#xff0c;成为实现充电桩智能化管理的关键。 公交充电桩运维管理需求概述&#xff1a; 1.实时性&#xff1a;实时监控充电状态、剩…...

matlab 四维数据可视化(已解决)

虽然这不是传统意义上的“4维可视化”&#xff0c;但你可以通过在三维空间中表示两个维度来间接展示4维数据。例如&#xff0c;你可以使用颜色来表示第四个维度。 clc clear close all% 假设X, Y, Z为你的三维数据&#xff0c;C为第四维数据 X rand(100, 1); Y rand(100, 1);…...

歌曲分类和流行度预测

1. 项目介绍 本项目从kaggle平台上下载了数据集&#xff0c;该数据集包含了3万多首来自Spotify API 的歌曲&#xff0c;共有23个特征。首先对数据集进行预处理&#xff0c;如重复行、缺失值、标准化处理等。再对预处理后的数据进行探索性分析&#xff0c;观察各变量的分布情况&…...

经验分享:用一张表解决并发冲突!数据库事务锁的核心实现逻辑

背景 对于一些内部使用的管理系统来说&#xff0c;可能没有引入Redis&#xff0c;又想基于现有的基础设施处理并发问题&#xff0c;而数据库是每个应用都避不开的基础设施之一&#xff0c;因此分享个我曾经维护过的一个系统中&#xff0c;使用数据库表来实现事务锁的方式。 之…...

oracle decode

1. 基本语法 DECODE(expression, search1, result1, search2, result2, ..., default_result) expression &#xff1a;需要比较的表达式或列。search1, search2, ... &#xff1a;要匹配的值。result1, result2, ... &#xff1a;当 expression 等于 search 时返回的结果。def…...

让后台界面布局更灵活:在GrapesJS中复刻Java的五区式布局

当你想要在可视化编辑器中做一个类似Java BorderLayout 的五区布局&#xff0c;却发现市面上大多只能“简单拼接”而难以自由扩展时&#xff0c;你或许就需要一个更灵活的布局管理器来帮忙。本篇文章就从这个痛点开始&#xff0c;带你一步步揭秘如何用 GrapesJS 自定义并实现一…...

【网络安全 | 漏洞挖掘】分享21个基础漏洞案例

未经许可,不得转载。 文章目录 案例1:绕过500状态码案例2:修改前端实现任意文件上传案例3:Nmap扫描端口命令案例4:绕过限制实现任意文件读取案例5:删除任意目录文件案例6:锁定任意账户案例7:重置任意用户密码案例8:接管任意账户方法一方法二案例9:功能校验机制绕过案…...

期权适合什么类型的投资者交易?

财顺小编本文主要介绍期权适合什么类型的投资者交易&#xff1f;期权适合的投资者类型需结合其风险偏好、投资目标及市场判断能力综合评估。 期权适合什么类型的投资者交易&#xff1f; 1. 风险管理型投资者&#xff08;稳健型&#xff09; 适用场景&#xff1a;持有股票、大…...

浅谈C++/C命名冲突

前言 在这里我会简要地介绍产生命名冲突的原因&#xff0c;和C中处理命名冲突的方法&#xff0c;同时和C语言的解决办法进行比较。 相信你在阅读完之后一定会有收获。对于我们来说&#xff0c;了解编译器的编译链接过程才能更好的理解编译器是如何报错的&#xff0c;更能让我们…...

【星云 Orbit • STM32F4】08. 用判断数据头来接收据的串口通用程序框架

【星云 Orbit • STM32F4】08. 用判断数据头来接收据的串口通用程序框架 1. 引言 本教程旨在帮助嵌入式开发小白从零开始&#xff0c;学习如何在STM32F407微控制器上实现一个基于串口的数据接收程序。该程序能够通过判断数据头来接收一串数据&#xff0c;并将其存储到缓冲区中…...

C# OnnxRuntime部署DAMO-YOLO香烟检测

目录 说明 效果 模型信息 项目 代码 下载 参考 说明 效果 模型信息 Model Properties ------------------------- --------------------------------------------------------------- Inputs ------------------------- name&#xff1a;input tensor&#xff1a;Floa…...

探索Elasticsearch:索引的CRUD

在企业环境中&#xff0c;Elasticsearch的索引CRUD&#xff08;创建Create、读取Read、更新Update、删除Delete&#xff09;操作是非常基础且频繁使用的功能。这些操作对于管理和维护数据至关重要&#xff0c;尤其是在处理大规模数据集和需要实时搜索与分析的应用场景中。 目录…...

C++:多态与虚函数

1.虚函数&#xff0c;在函数前加virtual即可。有虚函数时&#xff0c;父类指针指向父类对象时就会使用父类的成员&#xff0c;指向子类对象时就可以使用子类成员&#xff0c;进而我们引入了多态的概念。 2.多态&#xff1a;父类指针指向子类的对象&#xff0c;通过父类指针调用…...

【Python 数据结构 2.时间复杂度和空间复杂度】

Life is a journey —— 25.2.28 一、引例&#xff1a;穷举法 1.单层循环 所谓穷举法&#xff0c;就是我们通常所说的枚举&#xff0c;就是把所有情况都遍历了的意思。 例&#xff1a;给定n&#xff08;n ≤ 1000&#xff09;个元素ai&#xff0c;求其中奇数有多少个 判断一…...

【Qt QML】QML鼠标事件(MouseArea)

QML鼠标事件全面解析 一、MouseArea基础概念 在 QML 中,鼠标事件是处理用户与界面元素交互的重要部分。QML 提供了多种方式来处理鼠标事件,MouseArea 是 QML 中用于处理鼠标事件的核心元素,它可以覆盖在其他元素之上,捕获鼠标操作并触发相应的信号。 1、基本用法 import …...

医脉云枢:中医药典籍知识图谱与非遗传承多维可视化系统

核心优势&#xff1a; "医脉"直击主题&#xff0c;"云枢"体现技术前瞻性 "非遗传承"呼应二十大文化政策 "多维"涵盖3D模型、时间轴、地图等多种可视化形式 技术栈&#xff1a;Vue Flask Element UI ECharts MySQL 同时参考了…...

vue 和 react 底层采用的 diff 算法的区别

Vue 3 和 React 在底层 Diff 算法上的实现确实有一些区别&#xff0c;主要体现在设计理念、性能优化策略以及具体实现方式上。以下是对两者 Diff 算法差异的详细分析&#xff1a; 1. 总体设计理念 Vue 3 的 Diff 算法 Vue 3 的虚拟 DOM Diff 算法基于“双端比较”思想&#xff…...

养老小程序方案详解居家养老小程序系统

养老小程序&#xff0c;上门居家养老小程序&#xff0c;用户端护工端小程序&#xff0c;管理后台。php开发语言&#xff0c;可源码搭建&#xff0c;二次开发或者定制开发。 一 用户端&#xff1a;小程序 核心功能模块&#xff1a;用户完善个人健康档案&#xff0c;在线选择服…...

Tauri跨平台开发问题及解决方案深度解析(React版)

Tauri跨平台开发问题及解决方案深度解析&#xff08;React版&#xff09; 一、环境配置与项目初始化难题&#xff08;React适配&#xff09; 1.1 React项目初始化 推荐模板&#xff1a; # 使用ReactTypeScript模板 npm create tauri-applatest -- --template react-ts# 项目…...

【OMCI实践】omci.lua脚本文件(独家分享)

引言 omci.lua文件是Wireshark的OMCI协议解析插件的核心组件。它配合BinDecHex.lua&#xff0c;可以解析OMCI协议的数据包&#xff0c;提取出消息类型、受管实体标识、受管实体属性等关键信息&#xff0c;并以人类可读的形式显示在Wireshark的解码视图中&#xff0c;方便研发人…...

React高级内容探索

flushSync确保了DOM立即更新 flushSync让你强制React同步刷新提供回调中的任何更新&#xff0c;这确保了DOM立即更新 flushSync是DOM更新之后的&#xff0c;像vue中的nextTick&#xff1a; import { useState,useRef} from "react" import { flushSync} from &quo…...

前端水印实现方式

一、简介 简单来说&#xff0c;前端水印就是在网页或应用程序的前端界面上添加的一种标记&#xff0c;通常是文本、图标或图案等形式。它就像给你的数字内容贴上了一个独特的 “标签”&#xff0c;用于标识内容的归属、防止未经授权的使用和传播。比如&#xff0c;一些在线图片…...

【新手入门】SQL注入之getshell(木马)

木马介绍 木马其实就是一段程序&#xff0c;这个程序运行到目标主机上时&#xff0c;主要可以对目标进行远程控制、盗取信息等功能&#xff0c;一般不会破坏目标主机&#xff0c;当然&#xff0c;这也看黑客是否想要搞破坏。 按照功能分类:远控型、破坏型、流氓软件型、盗取信…...

Git操作指南:分支合并、回退及其他重要操作

在软件开发的协作过程中&#xff0c;Git 作为一款强大的版本控制系统&#xff0c;能帮助开发者高效管理代码的各个版本和分支。本文将详细介绍 Git 中常见的分支合并、取消本地修改、回退操作等&#xff0c;并提供通俗易懂的解释和步骤指南。 一、分支合并 分支合并是 Git 工…...

Vue 3 引入全局状态管理 pinia

什么是全局状态管理? 所有页面全局共享的变量&#xff0c;而不是局限在某一个页面中。适合作为全局状态的数据: 已登录用户信息 (每个页面几乎都要用) Pinia 是一个主流的状态管理库&#xff0c;相比于 Vuex 来说使用更简单&#xff0c;可参考 入门文档 开始 | Pinia 进行引…...

SQL 中为什么参数多了not in 比 in 慢多了,怎么优化

开发工作中&#xff0c;我发现一个现象&#xff0c;比喻下面的两个语句&#xff1a; select * from shangpin where spdm in (1,2,3,...); select * from shangpin where spdm not in (1,2,3,...); 当参数比较少的时候还看不出来什么&#xff0c;但是遇到参数上了几百几千&am…...

[密码学实战]Java生成SM2根证书及用户证书

前言 在国密算法体系中,SM2是基于椭圆曲线密码(ECC)的非对称加密算法,广泛应用于数字证书、签名验签等场景。本文将结合代码实现,详细讲解如何通过Java生成SM2根证书及用户证书,并深入分析其核心原理。 一、证书验证 1.代码运行结果 2.根证书验证 3.用户证书验证 二、…...

API接口:企业名称、注册号、统一社会信用代码、企业类型、成立日期和法定代表人等数据 API 接口使用指南

API接口&#xff1a;企业名称、注册号、统一社会信用代码、企业类型、成立日期和法定代表人等数据 API 接口使用指南 本文详细介绍一种基于 Web 搜索方式实现的企业信息查询接口&#xff0c;适用于数据补全、企业资质验证、信息查询等场景。文章内容涵盖接口功能、请求参数、返…...

版图自动化连接算法开发 00004 ------ 给定一个点,添加一个中间点实现 Manhattan 方式连接两个给定的坐标点

版图自动化连接算法开发 00004 ------ 给定一个点,添加一个中间点实现 Manhattan 方式连接两个给定的坐标点 引言正文引言 必读文章 ------ 版图自动化连接算法开发 00001 ------ 直接连接两个给定的坐标点。 此处,我们对给定点的坐标进行一下限制,因为是只添加一个点,因…...