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 圈的环长,恰好等于从链表头部到入环点的距离

相关文章:
LeetCode 142. 环形链表 II
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整…...
Leetcode刷题笔记题解(C++):224. 基本计算器
思路: step 1:使用栈辅助处理优先级,默认符号为加号。 step 2:遍历字符串,遇到数字,则将连续的数字字符部分转化为int型数字。 step 3:遇到左括号,则将括号后的部分送入递归&#x…...
还在为学MyBatis发愁?史上最全,一篇文章带你学习MyBatis
文章目录 前言一、📖MyBatis简介1.Mybatis历史2.MyBatis特性3.对比(其他持久化层技术) 二、📣搭建MyBatis1.开发环境2.创建maven工程3.创建MyBatis核心配置文件4.创建mapper接口5.创建MyBatis的映射文件6.通过junit测试功能7.加入…...
C# WPF上位机开发(树形控件在地图软件中的应用)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 前面我们聊过图形软件的开发方法。实际上,对于绘制的图形,我们一般还会用树形控件管理一下。举个例子,一个地图…...
【华为】文档中命令行约定格式规范(命令行格式规范、命令行行为规范、命令行参数格式、命令行规范)
文章目录 命令行约定格式**粗体:命令行关键字***斜体:命令行参数*[ ]:可选配置{ x | y | ... } 和 [ x | y | ... ]:选项{ x | y | ... }* 和 [ x | y | ... ]*:多选项&<1-n>:重复参数#ÿ…...
Trie 字典树(c++)(前缀)
题目链接:用户登录 题目: 样例: 输入 5 3 aaa aba aabbaa abbbbb cdd aabba abc abab 输出 Y N N 思路: 根据题目意思,要用到 Trie 字典树算法。 Trie 字典树,顾名思义,“字典”࿰…...
全球移动通信(2G/3G/4G/5G)频谱分布情况
一、概述 随着通信技术的不断发展,全球各国都在积极推进2G、3G、4G、5G网络的建设和应用。根据FCC统计,目前全球移动通信频谱分布如下: 二、分布 (一)俄罗斯 2G:主要使用900MHz和1800MHz两个频段。其中&…...
【04】GeoScene导出海图或者电子航道图000数据成果
1创建一个带有覆盖面和定义的产品 如果你没有已存在的S-57数据,你可以通过捕捉新的产品覆盖范围(多边形产品范围)及其所需的产品定义信息(产品元数据)来为新产品创建基础。 注: 如果你已经有一个S-57数据…...
安卓端出现https请求失败(转)
背景# 某天早上,正在一个会议时,突然好几个同事被叫出去了;后面才知道,是有业务同事反馈到领导那里,我们app里面某个功能异常。 具体是这样,我们安卓版本的app是禁止截屏的(应该是app里做了拦…...
appium2.0.1安装完整教程+uiautomator2安装教程
第一步:根据官网命令安装appium(Install Appium - Appium Documentation) 注意npm前提是设置淘宝镜像: npm config set registry https://registry.npmmirror.com/ 会魔法的除外。。。 npm i --locationglobal appium或者 npm…...
Hbase的Rowkey设计
Hbase的Rowkey设计 rowkey设计 # 1)长度原则# 最大64KB,推荐长度10~100 byte# 最好设为8的倍数,能短则短,rowkey如果太长会影响性能。# 2)唯一原则:rowkey应该具备唯一性# 3)散列原则…...
软考机考考试第一批经验分享
由于机考的特殊性,考试环境与传统笔试环境有所不同。下面是与考试环境相关的总结: 草稿纸:考场提供足够数量的草稿纸,每位考生都会分发一张白纸作为草稿纸。在草稿纸上需要写上准考证号。如果不够用,可以向监考老师再次…...
架构简洁之道有感,谈谈软件组件聚合的张力
配图由腾讯混元助手生成 这篇文章介绍了软件架构设计中组件设计思想,围绕“组件间聚合的张力”这个有意思的角度,介绍了概念,并且结合架构设计示例对这个概念进行了进一步阐述。 组件聚合?张力?这标题,有种…...
计算机网络 网络层上 | IP数据报,IP地址,ICMP,ARP等
文章目录 1 网络层的两个层面2 网络协议IP2.1 虚拟互联网络2.2 IP地址2.2.1 固定分类编址方式2.2.2 无分类编制CIDR2.2.3 MAC地址和IP地址区别 2.3 地址解析协议ARP2.3.1 解析过程 2.4 IP数据报格式 3 IP层转发分组流程4 国际控制报文协议ICMP4.1 ICMP格式结构4.2 分类4.2.1 差…...
金智融门户(统一身份认证)同步数据至钉钉通讯录
前言:因全面使用金智融门户和数据资产平台,二十几个信息系统已实现统一身份认证和数据同步,目前单位使用的钉钉尚未同步组织机构和用户信息,职工入职、离职、调岗时都需要手工在钉钉后台操作,一是操作繁琐,二是钉钉通讯录更新不及时或经常遗漏,带来管理问题。通过金智融…...
服务器RAID配置及功能介绍
服务器RAID配置及功能介绍 一、RAID磁盘阵列详解1.RAID磁盘阵列介绍2.RAID 03.RAID14.RAID35.RAID56.RAID67.RAID 10总结阵列卡介绍 一、RAID磁盘阵列详解 1.RAID磁盘阵列介绍 ①是Redundant Array of lndependent Disks的缩写中文简称为独立冗余磁盘阵列。 ②把多块独立的物…...
vue + element 实现鼠标左右滑动效果
我用了element中的走马灯+overflow-x: auto; html (复制后格式化一下) <div class"scroll" id"entrance"><el-carousel height"150px" :autoplay"false" :loop"false" arrow&q…...
gitlab 安装
1.安装依赖 sudo apt updatesudo apt-get upgradesudo apt-get install curl openssh-server ca-certificates postfix安装gitlab curl -s https://packages.gitlab.com/install/repositories/gitlab/gitlab-ce/script.deb.sh | sudo bash官网下载安装包 要选ubuntu focal 安…...
idea中定时+多数据源配置
因项目要求,需要定时从达梦数据库中取数据,并插入或更新到ORACLE数据库中 1.pom.xml <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-…...
Python---多任务的介绍
1. 提问 利用现学知识能够让两个函数或者方法同时执行吗? 不能,因为之前所写的程序都是单任务的,也就是说一个函数或者方法执行完成另外一个函数或者方法才能执行,要想实现这种操作就需要使用多任务。 多任务的最大好处是充分利用CPU资源&…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
基于Springboot+Vue的办公管理系统
角色: 管理员、员工 技术: 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能: 该办公管理系统是一个综合性的企业内部管理平台,旨在提升企业运营效率和员工管理水…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...
