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

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 &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内部使用整…...

Leetcode刷题笔记题解(C++):224. 基本计算器

思路&#xff1a; step 1&#xff1a;使用栈辅助处理优先级&#xff0c;默认符号为加号。 step 2&#xff1a;遍历字符串&#xff0c;遇到数字&#xff0c;则将连续的数字字符部分转化为int型数字。 step 3&#xff1a;遇到左括号&#xff0c;则将括号后的部分送入递归&#x…...

还在为学MyBatis发愁?史上最全,一篇文章带你学习MyBatis

文章目录 前言一、&#x1f4d6;MyBatis简介1.Mybatis历史2.MyBatis特性3.对比&#xff08;其他持久化层技术&#xff09; 二、&#x1f4e3;搭建MyBatis1.开发环境2.创建maven工程3.创建MyBatis核心配置文件4.创建mapper接口5.创建MyBatis的映射文件6.通过junit测试功能7.加入…...

C# WPF上位机开发(树形控件在地图软件中的应用)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 前面我们聊过图形软件的开发方法。实际上&#xff0c;对于绘制的图形&#xff0c;我们一般还会用树形控件管理一下。举个例子&#xff0c;一个地图…...

【华为】文档中命令行约定格式规范(命令行格式规范、命令行行为规范、命令行参数格式、命令行规范)

文章目录 命令行约定格式**粗体&#xff1a;命令行关键字***斜体&#xff1a;命令行参数*[ ]&#xff1a;可选配置{ x | y | ... } 和 [ x | y | ... ]&#xff1a;选项{ x | y | ... }* 和 [ x | y | ... ]*&#xff1a;多选项&<1-n>&#xff1a;重复参数#&#xff…...

Trie 字典树(c++)(前缀)

题目链接&#xff1a;用户登录 题目&#xff1a; 样例&#xff1a; 输入 5 3 aaa aba aabbaa abbbbb cdd aabba abc abab 输出 Y N N 思路&#xff1a; 根据题目意思&#xff0c;要用到 Trie 字典树算法。 Trie 字典树&#xff0c;顾名思义&#xff0c;“字典”&#xff0…...

全球移动通信(2G/3G/4G/5G)频谱分布情况

一、概述 随着通信技术的不断发展&#xff0c;全球各国都在积极推进2G、3G、4G、5G网络的建设和应用。根据FCC统计&#xff0c;目前全球移动通信频谱分布如下&#xff1a; 二、分布 &#xff08;一&#xff09;俄罗斯 2G&#xff1a;主要使用900MHz和1800MHz两个频段。其中&…...

【04】GeoScene导出海图或者电子航道图000数据成果

1创建一个带有覆盖面和定义的产品 如果你没有已存在的S-57数据&#xff0c;你可以通过捕捉新的产品覆盖范围&#xff08;多边形产品范围&#xff09;及其所需的产品定义信息&#xff08;产品元数据&#xff09;来为新产品创建基础。 注&#xff1a; 如果你已经有一个S-57数据…...

安卓端出现https请求失败(转)

背景# 某天早上&#xff0c;正在一个会议时&#xff0c;突然好几个同事被叫出去了&#xff1b;后面才知道&#xff0c;是有业务同事反馈到领导那里&#xff0c;我们app里面某个功能异常。 具体是这样&#xff0c;我们安卓版本的app是禁止截屏的&#xff08;应该是app里做了拦…...

appium2.0.1安装完整教程+uiautomator2安装教程

第一步&#xff1a;根据官网命令安装appium&#xff08;Install Appium - Appium Documentation&#xff09; 注意npm前提是设置淘宝镜像&#xff1a; npm config set registry https://registry.npmmirror.com/ 会魔法的除外。。。 npm i --locationglobal appium或者 npm…...

Hbase的Rowkey设计

Hbase的Rowkey设计 rowkey设计 # 1&#xff09;长度原则# 最大64KB&#xff0c;推荐长度10~100 byte# 最好设为8的倍数&#xff0c;能短则短&#xff0c;rowkey如果太长会影响性能。# 2&#xff09;唯一原则&#xff1a;rowkey应该具备唯一性# 3&#xff09;散列原则…...

软考机考考试第一批经验分享

由于机考的特殊性&#xff0c;考试环境与传统笔试环境有所不同。下面是与考试环境相关的总结&#xff1a; 草稿纸&#xff1a;考场提供足够数量的草稿纸&#xff0c;每位考生都会分发一张白纸作为草稿纸。在草稿纸上需要写上准考证号。如果不够用&#xff0c;可以向监考老师再次…...

架构简洁之道有感,谈谈软件组件聚合的张力

配图由腾讯混元助手生成 这篇文章介绍了软件架构设计中组件设计思想&#xff0c;围绕“组件间聚合的张力”这个有意思的角度&#xff0c;介绍了概念&#xff0c;并且结合架构设计示例对这个概念进行了进一步阐述。 组件聚合&#xff1f;张力&#xff1f;这标题&#xff0c;有种…...

计算机网络 网络层上 | 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中的走马灯&#xff0b;overflow-x: auto; html &#xff08;复制后格式化一下&#xff09; <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. 提问 利用现学知识能够让两个函数或者方法同时执行吗? 不能&#xff0c;因为之前所写的程序都是单任务的&#xff0c;也就是说一个函数或者方法执行完成另外一个函数或者方法才能执行&#xff0c;要想实现这种操作就需要使用多任务。 多任务的最大好处是充分利用CPU资源&…...

C标准库缓冲区溢出问题与安全编程实践

1. C标准库缓冲区溢出问题概述缓冲区溢出是C语言开发中最常见的安全漏洞之一。作为一名有十年经验的嵌入式开发者&#xff0c;我见过太多由于不当使用标准库函数导致的崩溃和安全问题。缓冲区溢出通常发生在程序向固定大小的缓冲区写入超过其容量的数据时&#xff0c;多余的数据…...

JDK 17 + Spring Boot 3.5.8:企业级开发技术栈全景分析

JDK 17与Spring Boot 3.5.8的核心特性JDK 17 LTS特性 JDK 17作为长期支持版本&#xff08;LTS&#xff09;&#xff0c;提供多项生产级增强&#xff1a;密封类&#xff08;Sealed Classes&#xff09;&#xff1a;通过sealed和permits关键字限制类的继承关系&#xff0c;增强领…...

SonarQube实战:通过pom.xml配置sonar-maven-plugin实现自动化代码扫描

1. 为什么需要自动化代码扫描 在软件开发过程中&#xff0c;代码质量是决定项目成败的关键因素之一。想象一下&#xff0c;你正在建造一栋房子&#xff0c;如果砖块质量不过关&#xff0c;水泥配比不对&#xff0c;即使外观再漂亮&#xff0c;也可能随时倒塌。代码也是如此&…...

Qwen3.5-9B多模态能力:手写公式识别+LaTeX代码生成效果展示

Qwen3.5-9B多模态能力&#xff1a;手写公式识别LaTeX代码生成效果展示 1. 模型核心能力概览 Qwen3.5-9B是一款拥有90亿参数的开源大语言模型&#xff0c;在多模态理解和处理方面表现出色。这个模型特别适合处理需要结合图像和文本信息的复杂任务&#xff0c;比如手写公式识别…...

BiliBiliCCSubtitle:3分钟掌握B站字幕下载与格式转换的终极指南

BiliBiliCCSubtitle&#xff1a;3分钟掌握B站字幕下载与格式转换的终极指南 【免费下载链接】BiliBiliCCSubtitle 一个用于下载B站(哔哩哔哩)CC字幕及转换的工具; 项目地址: https://gitcode.com/gh_mirrors/bi/BiliBiliCCSubtitle 你是否经常需要从B站视频中提取字幕内…...

磁流变半主动悬架Simulink模型创建与策略设计详解

磁流变半主动悬架simulink模型&#xff0c;包含模型创建&#xff0c;模型策略设计磁流变悬架的Simulink建模就像搭积木——你得先搞清楚每块积木该放哪儿。咱们从最基础的四分之一车模型开始&#xff0c;车身质量、悬架刚度这些参数直接在Simulink里拖几个Mass和Spring模块就能…...

为什么你的Java车载服务在-40℃冷启动失败?温度敏感型ClassLoader加载异常的12小时紧急修复路径

第一章&#xff1a;为什么你的Java车载服务在-40℃冷启动失败&#xff1f;温度敏感型ClassLoader加载异常的12小时紧急修复路径低温环境并非仅影响硬件可靠性——JVM 的类加载机制在极端低温下会触发底层文件系统与内存映射的隐式行为偏移。某车规级 Java 服务在-40℃冷启动时反…...

自动驾驶开发必备:Vscode+Git双神器组合的隐藏技巧(含分支管理秘籍)

自动驾驶开发必备&#xff1a;VscodeGit双神器组合的隐藏技巧&#xff08;含分支管理秘籍&#xff09; 在自动驾驶开发领域&#xff0c;高效的代码管理和协作流程是项目成功的关键因素。随着代码库规模不断扩大&#xff0c;团队规模持续增长&#xff0c;传统的版本控制方式往往…...

无代码自动化:OpenClaw+Qwen3.5-9B可视化流程搭建

无代码自动化&#xff1a;OpenClawQwen3.5-9B可视化流程搭建 1. 为什么选择OpenClawQwen3.5-9B组合 去年夏天&#xff0c;我发现自己每周要花3小时重复做三件事&#xff1a;整理会议录音、提取待办事项、设置日历提醒。当我尝试用传统自动化工具时&#xff0c;要么需要写代码…...

一篇大模型Agents工作流优化最新综述

过去&#xff0c;人们总希望一个LLM直接把任务做完&#xff1b;现在&#xff0c;一个更现实的方向正在浮现——针对不同任务设计不同工作流&#xff0c;并让系统在执行前、执行中乃至执行后持续优化这条链路。 近日&#xff0c;Rensselaer Polytechnic Institute&#xff08;RP…...