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

【LeetCode】环形链表 II [M](链表)

142. 环形链表 II - 力扣(LeetCode)

一、题目

给定一个链表的头节点  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 <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

二、代码

/*** 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) {// 过滤空链表、单节点链表和双节点链表,这三种情况一定是无环链表,直接返回nullif (head == null || head.next == null || head.next.next == null) {return null;}// 设置两个快慢指针,快指针一次走两步,满指针一次走一步// 提前将快慢指针的初始位置设置好,这一步很重要,不能将初始位置都设置成head,会导致结果错误ListNode slow = head.next; // n1 -> slowListNode fast = head.next.next; // n2 -> fastwhile (fast != slow) {// 如果快指针在遍历过程中出现了结尾为空的情况,直接返回null,表示一定没有环if (fast.next == null || fast.next.next == null) {return null;}// 快指针一次走两步fast = fast.next.next;// 慢指针一次走一步slow = slow.next;}// 执行到这里说明快慢指针重合了,此时将快指针重新回到头节点fast = head;// 快慢指针都用相同的步长向后遍历,当再次相遇的时候,相遇节点就是第一个入换节点while (fast != slow) {fast = fast.next;slow = slow.next;}// 返回入环节点return fast;}
}

三、解题思路 

用快慢指针解决这个问题,就是设置两个快慢指针从头开始向后遍历链表(快指针一次走两步,慢指针一次走1步),如果快指针遍历到了null,就说明该节点没有环,因为有环节点不可能有节点next指向null。如果快指针和慢指针再次相会,就说明快指针已经沿着链表转了一圈又转回来了,再次追上了慢指针,比慢指针多跑了一圈。这个时候慢指针保持在相遇位置,快指针再次回到链表头节点,两个指针再次以相同的步长向后遍历(全都一次只走一步),这样当两个节点再次相遇的时候,相遇节点就是该链表的入环节点(这个过程中,慢指针就是一直在环中转圈,快指针当走到入环节点的时候,慢指针也会转圈转到入环节点)。

相关文章:

【LeetCode】环形链表 II [M](链表)

142. 环形链表 II - 力扣&#xff08;LeetCode&#xff09; 一、题目 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链…...

Unity之如何实现一个VR任务(剧情)系统

一.前言 最近再做一个VR项目,里面有大量的剧情和VR操作任务。 比如: 1.张三说了什么话,干了什么事,然后,李四又说了什么,做了什么动画,完了之后,场景中某个物体高亮,让我们触摸或者射线点击(pc的话鼠标点击)和其发生交互。 2.我们使用VR手柄或者鼠标与场景中的一个…...

k8s核心概念与kubectl命令行工具的使用

k8s官方文档Kubernetes 文档 | Kubernetes作用&#xff1a;kubernetes用于容器化应用程序的部署&#xff0c;扩展和管理。目标&#xff1a;是让部署容器化应用简单高效。Kubernetes集群架构与组件 Master组件 kube-apiserverkubernetes API&#xff0c;集群的统一入口&#xff…...

【零基础入门前端系列】—无序列表、有序列表、定义列表(四)

一、HTML无序列表 无序列表是一个项目的列表&#xff0c;此列项目使用粗体圆点&#xff08;典型的小黑圆圈&#xff09;进行标记。 无序列表使用 <ul> 标签 <ul> <li>Coffee</li> <li>Milk</li> </ul>嵌套结构&#xff1a; <…...

为什么重写equals还要重写hashcode方法

目录equals方法hashCode方法为什么要一起重写&#xff1f;总结面试如何回答重写 equals 时为什么一定要重写 hashCode&#xff1f;要想了解这个问题的根本原因&#xff0c;我们还得先从这两个方法开始说起。 以下是关于hashcode的一些规定&#xff1a; 两个对象相等&#xff0…...

电子技术——电流镜负载的差分放大器

电子技术——电流镜负载的差分放大器 目前我们学习的差分放大器都是使用的是差分输出的方式&#xff0c;即在两个漏极之间获取电压。差分输出主要有以下优势&#xff1a; 降低了共模信号的增益&#xff0c;提高了共模抑制比。降低了输入偏移电压。提升了差分输入的增益。 由于…...

go面试题

1.json包在使用的时候&#xff0c;结构体里的变量不加tag能不能正常转成json里的字段&#xff1f; 如果变量首字母小写&#xff0c;则为private。无论如何不能转&#xff0c;因为取不到反射信息。如果变量首字母大写&#xff0c;则为public。 不加tag&#xff0c;可以正常转为j…...

攻防世界-Confusion1

题目 访问题目场景 某天&#xff0c;Bob说&#xff1a;PHP是最好的语言&#xff0c;但是Alice不赞同。所以Alice编写了这个网站证明。在她还没有写完的时候&#xff0c;我发现其存在问题。(请不要使用扫描器) 然后结合图片我们知道&#xff0c;这个网址是python写的&#xff0…...

机器学习实战--梯度下降法进行波士顿房价预测

前言&#xff1a; Hello大家好&#xff0c;我是Dream。 今天来学习一下如何使用机器学习梯度下降法进行波士顿房价预测&#xff0c;这是简单的一个demo&#xff0c;主要展示的是一些小小的思路~ 本文目录&#xff1a;一、波士顿房价预测1.全部的数据可视化2.地理数据可视化3.房…...

黑马】后台管理-项目优化和上线

一。项目优化优化1&#xff0c;加载进度条显示安装一个运行依赖&#xff0c;nprogress然后导包&#xff0c;调用对象展示和隐藏在main中基于拦截器实现展示进度条和隐藏进度条的效果如果触发请求拦截器&#xff0c;证明发起请求&#xff0c;希望展示进度条&#xff0c;如果触发…...

Web 框架 Flask 快速入门(三)数据库-MySQL

课程地址&#xff1a;Python Web 框架 Flask 快速入门 文章目录数据库1、数据库的安装与配置2、数据库的简单使用——增删改1. 定义数据模型2. 增删改3、 关系引用——表的关联4、查询——通过SQLAlchemy扩展5、其他1. 数据模型的实现&#xff08;疑惑&#xff09;6、Bug记录1.…...

牛客网Python篇数据分析习题(六)

1.某公司计划举办一场运动会&#xff0c;现有运动会项目数据集items.csv。 包含以下字段&#xff1a; item_id&#xff1a;项目编号&#xff1b; item_name:项目名称&#xff1b; location:比赛场地。 有员工报名情况数据集signup.csv。包含以下字段&#xff1a; employee_id&a…...

Ansible的安装及部署

目录 一、Ansible对于企业运维的重大意义 二、Ansible的安装 三、构建Ansible清单 1.直接书写受管主机名或ip&#xff0c;每行一个 2.设定受管主机的组[组名称] 四、Ansible配置文件参数详解 1、配置文件的分类与优先级 2.配置新用户的Ansible配置 3.生成免密认证 本章…...

链表题目总结 -- 递归

目录一. 递归反转整个链表1. 思路简述2. 代码3. 总结二. 反转链表前 N 个节点1. 思路简述2. 代码3. 总结三、反转链表的一部分1. 思路简述2. 代码3.总结四、从节点M开始反转后面的链表1. 思路简述2. 代码3.总结一. 递归反转整个链表 题目链接&#xff1a;https://leetcode.cn/…...

重写-linux内存管理-伙伴分配器(一)

文章目录一、伙伴系统的结构二、初始化三、分配内存3.1 prepare_alloc_pages3.2 get_page_from_freelist3.2.1 zone_watermark_fast3.2.2 zone_watermark_ok3.2.3 rmqueue3.2.3.1 rmqueue_pcplist3.2.3.2 __rmqueue3.2.3.2.1 __rmqueue_smallest3.2.3.2.2 __rmqueue_fallback3.…...

为什么要用springboot进行开发呢?

文章目录前言1、那么Springboot是怎么实现自动配置的1.1 启动类1.2 SpringBootApplication1.3 Configuration1.4 ComponentScan1.5 EnableAutoConfiguration1.6 两个重要注解1.7 AutoConfigurationPackage注解1.8 Import(AutoConfigurationImportSelector.class)注解1.9自动配置…...

设备树信息解析相关函数

一。可以通过三种不同的方式解析设备树节点&#xff1a; 1.根据设备树节点的名字解析设备树节点 struct device_node *of_find_node_by_name(struct device_node *from, const char *name); 参数&#xff1a; from&#xff1a;当前节点父节点首地址 name:设备树节点名字 …...

LeetCode-1124. 表现良好的最长时间段【哈希表,前缀和,单调栈】

LeetCode-1124. 表现良好的最长时间段【哈希表&#xff0c;前缀和&#xff0c;单调栈】题目描述&#xff1a;解题思路一&#xff1a;查字典。cur是当前的前缀和(劳累与不劳累天数之差)&#xff0c;向前遍历。有两种情况。情况一&#xff0c;若cur大于0则是[0,i]的劳累与不劳累天…...

vue-router路由配置

介绍&#xff1a;路由配置主要是用来确定网站访问路径对应哪个文件代码显示的&#xff0c;这里主要描述路由的配置、子路由、动态路由&#xff08;运行中添加删除路由&#xff09; 1、npm添加 npm install vue-router // 执行完后会自动在package.json中添加 "vue-router…...

中国计算机设计大赛来啦!用飞桨驱动智慧救援机器狗

‍‍中国大学生计算机设计大赛是我国高校面向本科生最早的赛事之一&#xff0c;自2008年开赛至今&#xff0c;一直由教育部高校与计算机相关教指委等或独立或联合主办。大赛的目的是以赛促学、以赛促教、以赛促创&#xff0c;为国家培养德智体美劳全面发展的创新型、复合型、应…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...