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

【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

转载自&#xff1a;www.javaman.cn 1、整合springsecurity 添加pom.xml <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-security</artifactId> </dependency>2、springsecurity认证授权流程…...

脏读、不可重复读、幻读

一、脏读 A事务读取B事务尚未提交的数据&#xff0c;此时如果B事务发生错误并执行回滚操作&#xff0c;那么A事务读取到的数据就是脏数据。就好像原本的数据比较干净、纯粹&#xff0c;此时由于B事务更改了它&#xff0c;这个数据变得不再纯粹。这个时候A事务立即读取了这个脏…...

思维模型 反馈效应

本系列文章 主要是 分享 思维模型&#xff0c;涉及各个领域&#xff0c;重在提升认知。反馈促进改进。 1 反馈效应的应用 1.1 反馈效应在营销中的应用 1 “可口可乐与百事可乐之战” 在 20 世纪 80 年代&#xff0c;可口可乐公司是全球最大的饮料公司之一&#xff0c;其市场…...

【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^​w1​x1​...wd​xd​bw⊤xb. 代码实现 import torch from torch import nn from to…...

硝烟弥漫的科技战场——GPT之战

没想到2023年的双11之后&#xff0c;还能看到如此多的科技圈大佬针对GPT提出火药味十足的讨论和极具戏剧性的表演。 历史回顾&#xff1a; 11月6日&#xff0c;OpenAI发布会&#xff1a;GPT-4 Turbo模型、GPT应用商店、开源Whisper-large-v3等&#xff1b;11月17日&#xff0…...

re:Invent 构建未来:云计算生成式 AI 诞生科技新局面

文章目录 前言什么是云计算云计算类型亚马逊云科技云计算最多的功能最大的客户和合作伙伴社区最安全最快的创新速度最成熟的运营专业能力 什么是生成式 AI如何使用生成式 AI后记 前言 在科技发展的滚滚浪潮中&#xff0c;我们见证了云计算的崛起和生成式 AI 的突破&#xff0c…...

oneApi实现并⾏排序算法

零、OneApi简介 oneAPI是由英特尔推出的一个开放、统一的编程模型和工具集合&#xff0c;旨在简化跨不同硬件架构的并行计算。oneAPI的目标是提供一个统一的编程模型&#xff0c;使开发人员能够使用相同的代码在不同类型的硬件上进行并行计算&#xff0c;包括CPU、GPU、FPGA和…...

语音芯片的BUSY状态指示功能特征:提升用户体验与系统稳定性的关键

在电子产品的音频系统中&#xff0c;语音芯片扮演着至关重要的角色。为了保证音频的流畅播放和功能的正常运行&#xff0c;语音芯片的各种状态指示功能变得尤为重要。其中&#xff0c;BUSY状态指示功能是语音芯片中的一项关键特征&#xff0c;它对于提升用户体验和系统稳定性具…...

Leetcode2661. 找出叠涂元素

Every day a Leetcode 题目来源&#xff1a;2661. 找出叠涂元素 解法1&#xff1a;哈希 题目很绕&#xff0c;理解题意后就很简单。 由于矩阵 mat 中每一个元素都不同&#xff0c;并且都在数组 arr 中&#xff0c;所以首先我们用一个哈希表 hash 来存储 mat 中每一个元素的…...

免费最新6款热门SEO优化排名工具

网站的存在感对于业务和品牌的成功至关重要。在众多网站推广方法中&#xff0c;搜索引擎优化&#xff08;SEO&#xff09;是提高网站可见性的关键。而SEO的核心之一就是关键词排名。为了更好地帮助您优化网站。 SEO关键词排名工具 在如今信息过载的互联网时代&#xff0c;用户…...

绝地求生在steam叫什么?

绝地求生在Steam的全名是《PlayerUnknowns Battlegrounds》&#xff0c;简称为PUBG。作为一款风靡全球的多人在线游戏&#xff0c;PUBG于2017年3月23日正式上线Steam平台&#xff0c;并迅速成为一部热门游戏。 PUBG以生存竞技为核心玩法&#xff0c;玩家将被投放到一个辽阔的荒…...

Elasticsearch:什么是大语言模型(LLM)?

大语言模型定义 大语言模型 (LLM) 是一种深度学习算法&#xff0c;可以执行各种自然语言处理 (natural language processing - NLP) 任务。 大型语言模型使用 Transformer 模型&#xff0c;并使用大量数据集进行训练 —— 因此规模很大。 这使他们能够识别、翻译、预测或生成文…...

Kubernetes1.27容器化部署Prometheus

Kubernetes1.27容器化部署Prometheus GitHub链接根据自己的k8s版本选择对应的版本修改镜像地址部署命令对Etcd集群进行监控&#xff08;云原生监控&#xff09;创建Etcd Service创建Etcd证书的Secret创建Etcd ServiceMonitorgrafana导入模板成功截图 对MySQL进行监控&#xff0…...

fasterxml 注解组装实体

使用 FasterXML Jackson 的注解 JsonTypeInfo 和 JsonSubTypes 可以实现多态类型的处理。在你的 User 类上&#xff0c;你可以添加这些注解来指示 Jackson 如何处理多态类型。 以下是使用 JsonTypeInfo 和 JsonSubTypes 注解的 User 类的修改&#xff1a; import com.fasterx…...

自写一个函数将js对象转为Ts的Interface接口

如今的前端开发typescript 已经成为一项必不可以少的技能了&#xff0c;但是频繁的定义Interface接口会给我带来许多工作量&#xff0c;我想了想如何来减少这些非必要且费时的工作量呢&#xff0c;于是决定写一个函数&#xff0c;将对象放进它自动帮我们转换成Interface接口&am…...

【数据结构】拆分详解 - 二叉树的链式存储结构

文章目录 一、前置说明二、二叉树的遍历  1. 前序、中序以及后序遍历   1.1 前序遍历   1.2 中序遍历   1.3 后序遍历 2. 层序遍历 三、常见接口实现  0. 递归中的分治思想  1. 查找与节点个数   1.1 节点个数   1.2 叶子节点个数   1.3 第k层节…...

Laravel修改默认的auth模块为md5(password+salt)验证

首先声明&#xff1a;这里只是作为一个记录&#xff0c;实行拿来主义&#xff0c;懒得去记录那些分析源码的过程&#xff0c;不喜勿喷&#xff0c;可直接划走。 第一步&#xff1a;创建文件夹&#xff1a;app/Helpers/Hasher; 第二步&#xff1a;创建文件&#xff1a; app/Help…...

OpenStack-train版安装之安装Keystone(认证服务)、Glance(镜像服务)、Placement

安装Keystone&#xff08;认证服务&#xff09;、Glance&#xff08;镜像服务&#xff09;、Placement 安装Keystone&#xff08;认证服务&#xff09;安装Glance&#xff08;镜像服务&#xff09;安装Placement 安装Keystone&#xff08;认证服务&#xff09; 数据库创建、创…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...