LeetCode每日精进:142.环形链表II
题目链接:142.环形链表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 解释:链表中没有环。
提示:
- 链表中节点的数目范围在范围
[0, 104]内-105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
思路:参考环形链表I ,依旧使用快慢指针解决
参考环形链表I ,快慢指针一定会在环形链表中相遇。
以示例1为例:

head为链表的头结点,meet为快慢指针在环中的相遇点, 由图可以初步判断:
meet到入环的初始结点的距离等于head到入环的初始结点的距离。
证明:相遇点到入环起始结点的距离 = 链表头结点到入环起始结点的距离

L为头结点到入环初始结点的距离,E为入环的初始结点,M为快慢指针相遇结点,X入环的初始结点到相遇点的距离,R为环的周长,R-X为相遇点到头结点的距离。
在快慢指针相遇时,fast所走的路程为L+X+nR,slow所走的路程为L+X
又因为慢指针走一步,快指针走两步,有以下公式:
2*慢指针的路程 = 快指针的路程
代入快慢指针路程可以得到:
L = (n-1)R+(R-X),n = 1,2,3...
当n等于1时,即相遇时,快指针刚好绕环一圈,则L = R-X
故相遇点到入环起始结点的距离 = 链表头结点到入环起始结点的距离
代码实现:
ListNode* slow = head;ListNode* fast = head;ListNode* meet = NULL;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){meet = slow;break;}}
定义快慢指针,找到相遇结点meet,找到后跳出循环。
ListNode* left = head;ListNode* right = meet;while(right){ if (left == right){return left;}left = left->next;right = right->next;}
找到相遇点后,让头结点和相遇点同时往后遍历,找到入环的起始结点,若相遇点为空,直接返回NULL。
完整代码:
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {ListNode* slow = head;ListNode* fast = head;ListNode* meet = NULL;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){meet = slow;break;}}ListNode* left = head;ListNode* right = meet;while(right){ if (left == right){return left;}left = left->next;right = right->next;}return NULL;
}相关文章:
LeetCode每日精进:142.环形链表II
题目链接:142.环形链表II 题目描述: 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环…...
CPP集群聊天服务器开发实践(五):nginx负载均衡配置
1 负载均衡器的原理与功能 单台Chatserver可以容纳大约两万台客户端同时在线聊天,为了提升并发量最直观的办法需要水平扩展服务器的数量,三台服务器可以容纳六万左右的客户端。 负载均衡器的作用: 把client的请求按照负载均衡算法分发到具体…...
easyexcel解析excel文件的时候报错
easyexcel解析xls文件的时候,报错Exception in thread "main" com.alibaba.excel.exception.ExcelAnalysisException: java.lang.NoClassDefFoundError: org/objectweb/asm/Type at com.alibaba.excel.analysis.ExcelAnalyserImpl.analysis(ExcelAnalyser…...
Android设备 网络安全检测
八、网络与安全机制 6.1 网络框架对比 volley: 功能 基于HttpUrlConnection;封装了UIL图片加载框架,支持图片加载;网络请求的排序、优先级处理缓存;多级别取消请求;Activity和生命周期的联动(Activity结束生命周期同时取消所有网络请求 …...
word分栏使得最后一页内容自动平衡
word分栏使得最后一页内容自动平衡 Word中的分页符分节符 Word中的分页符与分节符统称为分隔符 【分页符】 是将一页内容分成两页, 但分离后的两页属于同一节;分页符用于强制在当前位置分页, 后续内容从下一页开始;分页符对应快捷键 Ctrl Enter ; 【分节符】 分节符用…...
完全免费稳定WebTerm网页版在线SSH连接,在线远程连接云服务器,可以控制背景,支持SFTP访问服务器文件。无需安装即可在线连接和管理服务器的SSH终端工具。支持跨平台设备。
目录 用途介绍 网页版SSH使用说明及教程 首次登录配置 设置中心介绍 编辑 SFTP功能 用途介绍 各位开发者在使用远程服务器时经常面临一个很致命的问题,就是当没有在使用自己电脑,远程服务器商家又没有提供在线的VNC连接,这时重新去安装…...
微信小程序医院挂号系统
第3章 系统设计 3.1系统体系结构 系统的体系结构非常重要,往往决定了系统的质量和生命周期。针对不同的系统可以采用不同的系统体系结构。本系统为微信小程序医院挂号系统,属于开放式的平台,所以在管理端体系结构中采用B/s。B/s结构抛弃了固…...
编程题-最大子数组和(中等-重点【贪心、动态规划、分治思想的应用】)
题目: 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组是数组中的一个连续部分。 解法一(枚举法-时间复杂度超限): …...
阿里云视频点播,基于thinkphp8上传视频
前端参考官方示例(jQuery版) <!DOCTYPE html> <html> <head><meta charset"utf-8"><title>阿里云 JavaScript上传SDK Demo (使用jquery)</title><script src"__STATIC__/jquery.min.js"></script><sc…...
《探秘AI绿色计算:降低人工智能硬件能耗的热点技术》
在人工智能飞速发展的当下,其硬件能耗问题愈发凸显。据国际能源署预测,人工智能的能源消耗可能大幅增长。因此,降低人工智能硬件能耗,实现绿色计算,已成为行业关键课题。以下是一些正在崭露头角的热点技术。 新型硬件…...
神经网络常见激活函数 9-CELU函数
文章目录 CELU函数导函数函数和导函数图像优缺点pytorch中的CELU函数tensorflow 中的CELU函数 CELU 连续可微指数线性单元:CELU(Continuously Differentiable Exponential Linear Unit),是一种连续可导的激活函数,结合了 ELU 和 …...
软考高级《系统架构设计师》知识点(四)
嵌入式技术 第二版新增内容 嵌入式系统:以应用为中心、以计算机技术为基础,并将可配置与可裁减的软、硬件、集成于一体的专用计算机系统,需要满足应用对功能、可靠性、成本、体积和功耗等方面的严格要求。一般嵌入式系统由嵌入式处理器、相关…...
opencv交叉编译
适用于瑞芯微,海思,酷芯等ARM平台。采用编译脚本配置编译选项,方便编译。 目录 一、创建目录 二、工具链配置 三、编译脚本 四、编译 一、创建目录 mikemike-virtual-machine:opencv-4.12/opencv/opencv$ tree . -L 1 . ├── 3rdpart…...
安装vite报错Install for [ ‘create-vite@latest‘ ] failed with code 1
报错内容: npm ERR! code ENOLOCAL npm ERR! Could not install from “Files\nodejs\node_cache_npx\31400” as it does not contain a package.json file. npm ERR! A complete log of this run can be found in: npm ERR! D:\Program Files\nodejs\node_cache_…...
Spring框架中都用到了哪些设计模式?
大家好,我是锋哥。今天分享关于【Spring框架中都用到了哪些设计模式?】面试题。希望对大家有帮助; Spring框架中都用到了哪些设计模式? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 Spring框架中使用了大量的设计模…...
LabVIEW 中 dotnet.llb 库功能
在 LabVIEW 功能体系里,位于 C:\Program Files (x86)\National Instruments\LabVIEW 2019\vi.lib\Platform\dotnet.llb 路径下的 dotnet.llb 库意义重大。作为与 .NET 技术交互的关键库,它使 LabVIEW 用户能够与基于 .NET 框架开发的应用程序和组件进行交…...
C# 变量,字段和属性的区别
总目录 前言 在C#中,变量(Variables)、字段(Fields) 和 属性(Properties) 是三个容易混淆但作用截然不同的概念。以下是它们的核心区别与使用场景: 一、变量(Variables&…...
wordpress模板文件结构超详解
wordpress网站建设中,主题的制作是最为核心的环节。了解模板文件结构是模板制作的第一步,本文所讲的模板文件结构包括两部分,一是指以文件名为概念的文件结构,二是指文件内容的代码结构。 一、如何使模板文件起作用 ↑ wordpres…...
android studio下载安装汉化-Flutter安装
1、下载android studio官方地址:(这个网址可能直接打不开,需要VPN) https://developer.android.com/studio?hlzh-cn mac版本分为X86和arm版本,电脑显示芯片是Inter的就是x86的,显示m1和m2的就是arm的 …...
数据开放共享和平台整合优化取得实质性突破的智慧物流开源了
智慧物流视频监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒,省去繁琐重复的适配流程,实现芯片、算法、应用的全流程组合,从而大大减少企业级应用约95%的开发成本可通过边缘计算技术…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...



