【LeeCode】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 解释:链表中没有环。
这道题目,不仅考察对链表的操作,而且还需要一些数学运算。
主要考察两知识点:
-
判断链表是否环
-
如果有环,如何找到这个环的入口
判断链表是否有环
可以使用快慢指针法,分别定义 fast 和 slow 指针,从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,如果 fast 和 slow指针在途中相遇 ,说明这个链表有环。
为什么fast 走两个节点,slow走一个节点,有环的话,一定会在环内相遇呢,而不是永远的错开呢
首先第一点:fast指针一定先进入环中,如果fast指针和slow指针相遇的话,一定是在环中相遇,这是毋庸置疑的。
那么来看一下,为什么fast指针和slow指针一定会相遇呢?
可以画一个环,然后让 fast指针在任意一个节点开始追赶slow指针。
会发现最终都是这种情况, 如下图:
fast和slow各自再走一步, fast和slow就相遇了
这是因为fast是走两步,slow是走一步,其实相对于slow来说,fast是一个节点一个节点的靠近slow的,所以fast一定可以和slow重合。
如果有环,如何找到这个环的入口
此时已经可以判断链表是否有环了,那么接下来要找这个环的入口了。
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。
那么相遇时: slow指针走过的节点数为: x + y, fast指针走过的节点数:x + y + n (y + z),n为fast指针在环内走了n圈才遇到slow指针, (y+z)为 一圈内节点的个数A。
因为fast指针是一步走两个节点,slow指针一步走一个节点, 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2:
(x + y) * 2 = x + y + n (y + z)
两边消掉一个(x+y): x + y = n (y + z)
因为要找环形的入口,那么要求的是x,因为x表示 头结点到 环形入口节点的的距离。
所以要求x ,将x单独放在左面:x = n (y + z) - y ,
再从n(y+z)中提出一个 (y+z)来,整理公式之后为如下公式:x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的,因为 fast指针至少要多走一圈才能相遇slow指针。
这个公式说明什么呢?
先拿n为1的情况来举例,意味着fast指针在环形里转了一圈之后,就遇到了 slow指针了。
当 n为1的时候,公式就化解为 x = z,
这就意味着,从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是 环形入口的节点。
也就是在相遇节点处,定义一个指针index1,在头结点处定一个指针index2。
让index1和index2同时移动,每次移动一个节点, 那么他们相遇的地方就是 环形入口的节点。
那么 n如果大于1是什么情况呢,就是fast指针在环形转n圈之后才遇到 slow指针。
其实这种情况和n为1的时候 效果是一样的,一样可以通过这个方法找到 环形的入口节点,只不过,index1 指针在环里 多转了(n-1)圈,然后再遇到index2,相遇点依然是环形的入口节点。
解:
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {// 有环ListNode index1 = fast;ListNode index2 = head;// 两个指针,从头结点和相遇结点,各走一步,直到相遇,相遇点即为环入口while (index1 != index2) {index1 = index1.next;index2 = index2.next;}return index1;}}return null;}
}
相关文章:
【LeeCode】142.环形链表II
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数…...
nodejs微信小程序+python+PHP健身房信息管理系统的设计与实现-计算机毕业设计推荐
目 录 摘 要 I ABSTRACT II 目 录 II 第1章 绪论 1 1.1背景及意义 1 1.2 国内外研究概况 1 1.3 研究的内容 1 第2章 相关技术 3 2.1 nodejs简介 4 2.2 express框架介绍 6 2.4 MySQL数据库 4 第3章 系统分析 5 3.1 需求分析 5 3.2 系统可行性分析 5 3.2.1技术可行性:…...
springboot集成springsecurity
转载自:www.javaman.cn 1、整合springsecurity 添加pom.xml <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-security</artifactId> </dependency>2、springsecurity认证授权流程…...
脏读、不可重复读、幻读
一、脏读 A事务读取B事务尚未提交的数据,此时如果B事务发生错误并执行回滚操作,那么A事务读取到的数据就是脏数据。就好像原本的数据比较干净、纯粹,此时由于B事务更改了它,这个数据变得不再纯粹。这个时候A事务立即读取了这个脏…...
思维模型 反馈效应
本系列文章 主要是 分享 思维模型,涉及各个领域,重在提升认知。反馈促进改进。 1 反馈效应的应用 1.1 反馈效应在营销中的应用 1 “可口可乐与百事可乐之战” 在 20 世纪 80 年代,可口可乐公司是全球最大的饮料公司之一,其市场…...
【PyTorch】线性回归
文章目录 1. 模型与代码实现2. Q&A 1. 模型与代码实现 模型 y ^ w 1 x 1 . . . w d x d b w ⊤ x b . \hat{y} w_1 x_1 ... w_d x_d b \mathbf{w}^\top \mathbf{x} b. y^w1x1...wdxdbw⊤xb. 代码实现 import torch from torch import nn from to…...
硝烟弥漫的科技战场——GPT之战
没想到2023年的双11之后,还能看到如此多的科技圈大佬针对GPT提出火药味十足的讨论和极具戏剧性的表演。 历史回顾: 11月6日,OpenAI发布会:GPT-4 Turbo模型、GPT应用商店、开源Whisper-large-v3等;11月17日࿰…...
re:Invent 构建未来:云计算生成式 AI 诞生科技新局面
文章目录 前言什么是云计算云计算类型亚马逊云科技云计算最多的功能最大的客户和合作伙伴社区最安全最快的创新速度最成熟的运营专业能力 什么是生成式 AI如何使用生成式 AI后记 前言 在科技发展的滚滚浪潮中,我们见证了云计算的崛起和生成式 AI 的突破,…...
oneApi实现并⾏排序算法
零、OneApi简介 oneAPI是由英特尔推出的一个开放、统一的编程模型和工具集合,旨在简化跨不同硬件架构的并行计算。oneAPI的目标是提供一个统一的编程模型,使开发人员能够使用相同的代码在不同类型的硬件上进行并行计算,包括CPU、GPU、FPGA和…...
语音芯片的BUSY状态指示功能特征:提升用户体验与系统稳定性的关键
在电子产品的音频系统中,语音芯片扮演着至关重要的角色。为了保证音频的流畅播放和功能的正常运行,语音芯片的各种状态指示功能变得尤为重要。其中,BUSY状态指示功能是语音芯片中的一项关键特征,它对于提升用户体验和系统稳定性具…...
Leetcode2661. 找出叠涂元素
Every day a Leetcode 题目来源:2661. 找出叠涂元素 解法1:哈希 题目很绕,理解题意后就很简单。 由于矩阵 mat 中每一个元素都不同,并且都在数组 arr 中,所以首先我们用一个哈希表 hash 来存储 mat 中每一个元素的…...
免费最新6款热门SEO优化排名工具
网站的存在感对于业务和品牌的成功至关重要。在众多网站推广方法中,搜索引擎优化(SEO)是提高网站可见性的关键。而SEO的核心之一就是关键词排名。为了更好地帮助您优化网站。 SEO关键词排名工具 在如今信息过载的互联网时代,用户…...
绝地求生在steam叫什么?
绝地求生在Steam的全名是《PlayerUnknowns Battlegrounds》,简称为PUBG。作为一款风靡全球的多人在线游戏,PUBG于2017年3月23日正式上线Steam平台,并迅速成为一部热门游戏。 PUBG以生存竞技为核心玩法,玩家将被投放到一个辽阔的荒…...
Elasticsearch:什么是大语言模型(LLM)?
大语言模型定义 大语言模型 (LLM) 是一种深度学习算法,可以执行各种自然语言处理 (natural language processing - NLP) 任务。 大型语言模型使用 Transformer 模型,并使用大量数据集进行训练 —— 因此规模很大。 这使他们能够识别、翻译、预测或生成文…...
Kubernetes1.27容器化部署Prometheus
Kubernetes1.27容器化部署Prometheus GitHub链接根据自己的k8s版本选择对应的版本修改镜像地址部署命令对Etcd集群进行监控(云原生监控)创建Etcd Service创建Etcd证书的Secret创建Etcd ServiceMonitorgrafana导入模板成功截图 对MySQL进行监控࿰…...
fasterxml 注解组装实体
使用 FasterXML Jackson 的注解 JsonTypeInfo 和 JsonSubTypes 可以实现多态类型的处理。在你的 User 类上,你可以添加这些注解来指示 Jackson 如何处理多态类型。 以下是使用 JsonTypeInfo 和 JsonSubTypes 注解的 User 类的修改: import com.fasterx…...
自写一个函数将js对象转为Ts的Interface接口
如今的前端开发typescript 已经成为一项必不可以少的技能了,但是频繁的定义Interface接口会给我带来许多工作量,我想了想如何来减少这些非必要且费时的工作量呢,于是决定写一个函数,将对象放进它自动帮我们转换成Interface接口&am…...
【数据结构】拆分详解 - 二叉树的链式存储结构
文章目录 一、前置说明二、二叉树的遍历 1. 前序、中序以及后序遍历 1.1 前序遍历 1.2 中序遍历 1.3 后序遍历 2. 层序遍历 三、常见接口实现 0. 递归中的分治思想 1. 查找与节点个数 1.1 节点个数 1.2 叶子节点个数 1.3 第k层节…...
Laravel修改默认的auth模块为md5(password+salt)验证
首先声明:这里只是作为一个记录,实行拿来主义,懒得去记录那些分析源码的过程,不喜勿喷,可直接划走。 第一步:创建文件夹:app/Helpers/Hasher; 第二步:创建文件: app/Help…...
OpenStack-train版安装之安装Keystone(认证服务)、Glance(镜像服务)、Placement
安装Keystone(认证服务)、Glance(镜像服务)、Placement 安装Keystone(认证服务)安装Glance(镜像服务)安装Placement 安装Keystone(认证服务) 数据库创建、创…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
