LeetCode 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, 10^4] 内
  • -10^5 <= Node.val <= 10^5
  • pos 的值为 -1 或者链表中的一个有效索引

进阶:你是否可以使用 O(1) 空间解决此题?

解法思路:

1、hash,遍历每个节点并记录,再次遍历到则存在环并返回

2、快慢指针,先判断是否有环,若有,则找出环的第一个节点(从相遇点到入环点的距离加上 n−1 圈的环长,恰好等于从链表头部到入环点的距离,使用第三个指针(初始化指向head),third 与 slow 刚好在入环处相遇)

法一:

/*** 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) {// hash// Time: O(n)// Space: O(n)ListNode pos = head;Set<ListNode> set = new HashSet<>();while (pos != null) {if (set.contains(pos)) {return pos;} else {set.add(pos);}pos = pos.next;}return null;}
}

 法二:

/*** 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) {// 快慢指针,先判断是否有环,若有,则找出环的第一个节点// 1. 判断是否有环if (head == null || head.next == null || head.next.next == null) return null;ListNode slow = head;ListNode fast = head;boolean hasCircle = false;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {hasCircle = true;break;}}// 2. 找出入环节点// 从相遇点到入环点的距离加上 n−1 圈的环长,恰好等于从链表头部到入环点的距离// 使用第三个指针(初始化指向head),third 与 slow 刚好在入环处相遇 if (hasCircle) {ListNode third = head;while (slow != third) {slow = slow.next;third = third.next;}return third;}return null;}
}

数学证明:从相遇点到入环点的距离加上 n−1 圈的环长,恰好等于从链表头部到入环点的距离 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/220720.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

运维实践|采集MySQL数据出现many connection errors

文章目录 问题出现问题分析当前环境问题分析 解决方案1 检查调度事件任务是否开启2 开启调度事件任务3 创建一张日志表4 创建函数存储过程5 创建事件定时器6 开启事件调度任务7 检查核实是否创建 总结 问题出现 最近在做OGG结构化数据采集工作&#xff0c;在数据采集过程中&am…

【微服务】Spring Aop原理深入解析

目录 一、前言 二、aop概述 2.1 什么是AOP 2.2 AOP中的一些概念 2.2.1 aop通知类型 2.3 AOP实现原理 2.3.1 aop中的代理实现 2.4 静态代理与动态代理 2.4.1 静态代理实现 三、 jdk动态代理与cglib代理 3.1 jdk动态代理 3.1.1 jdk代理示例 3.1.2 jdk动态代理模拟实现…

用23种设计模式打造一个cocos creator的游戏框架----(二十)解析器模式

1、模式标准 模式名称&#xff1a;解析器模式 模式分类&#xff1a;行为型 模式意图&#xff1a;给定一个语言&#xff0c;定义它的文法的一种表示&#xff0c;并定义一个解释器&#xff0c;这个解释器使用该表示来解释语言中的句子。 结构图&#xff1a; 适用于&#xff1…

TikTok矩阵玩法分享,如何建立TikTok矩阵?

矩阵是在 TikTok 上非常常见的营销方式&#xff0c;很多卖家想要通过矩阵化运营快速涨粉。但要想做好TikTok矩阵&#xff0c;需要有明确的方向和计划。下面东哥我将分享一些做TikTok矩阵的玩法&#xff0c;帮助大家更好地搭建自己的TikTok矩阵。 了解TikTok矩阵 TikTok矩阵是一…

Qt 数据库QSqlDatabase使用记录

记录一些在QT中使用QSqlDatabase操作数据库时&#xff0c;需要注意的地方 创建数据库 bool CDBOperatorAbstract::_openDBConn(CDatabaseConfig config) {QWriteLocker locker(&m_locker);QSqlDatabase db;if(QSqlDatabase::contains(m_connectionName)){db QSqlDatabas…

微信小程序校园跑腿系统怎么做,如何做,要做多久

​ 在这个互联网快速发展、信息爆炸的时代&#xff0c;人人都离不开手机&#xff0c;每个人都忙于各种各样的事情&#xff0c;大学生也一样&#xff0c;有忙于学习&#xff0c;忙于考研&#xff0c;忙着赚学分&#xff0c;忙于参加社团&#xff0c;当然也有忙于打游戏的&#x…

数据可视化---饼图、环形图、雷达图

类别内容导航机器学习机器学习算法应用场景与评价指标机器学习算法—分类机器学习算法—回归机器学习算法—聚类机器学习算法—异常检测机器学习算法—时间序列数据可视化数据可视化—折线图数据可视化—箱线图数据可视化—柱状图数据可视化—饼图、环形图、雷达图统计学检验箱…

PDF转为图片

PDF转为图片 背景pdf展示目标效果 发展过程最终解决方案&#xff1a;python PDF转图片pdf2image注意&#xff1a;poppler 安装 背景 最近接了一项目&#xff0c;主要的需求就是本地的文联单位&#xff0c;需要做一个电子刊物阅览的网站&#xff0c;将民族的刊物发布到网站上供…

LVS简介及LVS-NAT负载均衡群集的搭建

目录 LVS群集简介 群集的含义和应用场景 性能扩展方式 群集的分类 负载均衡&#xff08;LB&#xff09; 高可用&#xff08;HA&#xff09; 高性能运算&#xff08;HPC&#xff09; LVS的三种工作模式 NAT 地址转换 TUN IP隧道 IP Tunnel DR 直接路由 Direct Rout…

Xpath注入

这里学习一下xpath注入 xpath其实是前端匹配树的内容 爬虫用的挺多的 XPATH注入学习 - 先知社区 查询简单xpath注入 index.php <?php if(file_exists(t3stt3st.xml)) { $xml simplexml_load_file(t3stt3st.xml); $user$_GET[user]; $query"user/username[name&q…

SLAM学习——相机模型(针孔+鱼眼)

针孔相机模型 针孔相机模型是很常用&#xff0c;而且有效的模型&#xff0c;它描述了一束光线通过针孔之后&#xff0c;在针孔背面投影成像的关系&#xff0c;基于针孔的投影过程可以通过针孔和畸变两个模型来描述。 模型中有四个坐标系&#xff0c;分别为world&#xff0c;c…

机器学习 | SVM支持向量机

欲穷千里目&#xff0c;更上一层楼。 一个空间的混乱在更高维度的空间往往意味着秩序。 Machine-Learning: 《机器学习必修课&#xff1a;经典算法与Python实战》配套代码 - Gitee.com 1、核心思想及原理 针对线性模型中分类两类点的直线如何确定。这是一个ill-posed problem。…

Unity中URP下的菲涅尔效果实现(个性化修改)

文章目录 前言一、我们修正一下上篇文章中&#xff0c;可能遗留的Bug1、N向量 变为 单位向量2、使颜色范围在合理区间 二、实现菲涅尔效果强弱可自定义调节三、修改菲涅尔效果颜色1、在属性面板定义颜色属性2、在常量缓冲区申明该参数3、在片元着色器中&#xff0c;用颜色和菲涅…

使用 React 实现自定义数据展示日历组件

目录 背景实现日历组件父组件数据 效果最后 背景 项目中需要实现一个日历组件&#xff0c;并且需要展示月&#xff0c;日所对应的数据&#xff08;因为项目需求问题&#xff0c;就不统计年数据总量&#xff09;。网上找了一堆&#xff0c;基本都不大符合项目需求&#xff0c;且…

Java 基础学习(十一)File类与I/O操作

1 File类 1.1 File类概述 1.1.1 什么是File类 File是java.io包下作为文件和目录的类。File类定义了一些与平台无关的方法来操作文件&#xff0c;通过调用File类中的方法可以得到文件和目录的描述信息&#xff0c;包括名称、所在路径、读写性和长度等&#xff0c;还可以对文件…

计算机网络:物理层(编码与调制)

今天又学会了一个知识&#xff0c;加油&#xff01; 目录 一、基带信号与宽带信号 1、基带信号 2、宽带信号 3、选择 4、关系 二、数字数据编码为数字信号 1、非归零编码【NRZ】 2、曼彻斯特编码 3、差分曼彻斯特编码 4、归零编码【RZ】 5、反向不归零编码【NRZI】 …

Ubuntu安装ARM交叉编译器

Ubuntu安装交叉编译器 更新apt # 更新apt sudo apt update安装gcc sudo apt install build-essential查看gcc版本 gcc -v下载交叉编译工具 复制到用户目录 解压 tar -xvf gcc-linaro-5.5.0-2017.10-x86_64_arm-linux-gnueabihf.tar.xz移动到/opt/下 sudo ./gcc-linaro-5.…

环境搭建及源码运行_java环境搭建_maven

书到用时方恨少、觉知此时要躬行&#xff1b;拥有技术&#xff0c;成就未来&#xff0c;抖音视频教学地址&#xff1a;​​​​​​​ ​​​​​​​ 1、介绍 1&#xff09;管理项目依赖和版本 统一的项目依赖和版本管理 ​​​​​​​​​​​ 2&#xff09;Maven支持多模块…

创建型设计模式 | 原型模式

一、原型模式 1、原理 原型模式&#xff0c;用原型实例指定创建对象的种类&#xff0c;并且通过拷贝这些原型创建新的对象。原型模式其实就是从一个对象再创建另外一个可定制的对象&#xff0c;而且不需要知道任何创建的细节。原型像是一个模板&#xff0c;可以基于它复制好多…

如何让.NET应用使用更大的内存

我一直在思考为何Redis这种应用就能独占那么大的内存空间而我开发的应用为何只有4GB大小左右&#xff0c;在此基础上也问了一些大佬&#xff0c;最终还是验证下自己的猜测。 操作系统限制 主要为32位操作系统和64位操作系统。 每个进程自身还分为了用户进程空间和内核进程空…