【LeetCode】142.环形链表Ⅱ
题目
给定一个链表的头节点 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 <= 105pos的值为-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) {ListNode fast = head, slow = head;boolean flag = false;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {flag = true;break;}}if (!flag) {return null;}fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}return fast;}
}
总结
这题需要总结快指针慢指针走过路程的数学关系。
设快指针的路程为f,慢指针的路程为s,因为快指针每次经过两个节点,慢指针每次经过一个节点,则:
f = 2s
设链表非环形部分的节点数为a,环形部分的节点数为b,则:
f = a + k1b + c
s = a + k2b + c(c < b,k1 > k2)
结合以上两式可得:f = s + nb
那么:s = nb
由此我们可以知道慢指针路程为环形部分长度的整数倍,那么快慢指针相遇时,慢指针与环形部分入口处的距离就等于a。
相关文章:
【LeetCode】142.环形链表Ⅱ
题目 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部…...
16.Netty源码之ChannelPipeline
highlight: arduino-light 服务编排层:ChannelPipeline协调ChannelHandlerHandler EventLoop可以说是 Netty 的调度中心,负责监听多种事件类型:I/O 事件、信号事件、定时事件等,然而实际的业务处理逻辑则是由 ChannelPipeline 中所定义的 Cha…...
“使用Spring Boot构建微服务应用的最佳实践“
标题:使用Spring Boot构建微服务应用的最佳实践 摘要:本文将介绍如何使用Spring Boot构建微服务应用的最佳实践。我们将讨论微服务架构的概念、Spring Boot的优势以及一些最佳实践,同时提供示例代码帮助读者更好地理解和实践。 正文&#x…...
redis高可用之主从复制,哨兵,集群
目录 前言 一、主从复制 1、主从复制的作用 2、主从复制流程 3、部署Redis 主从复制步骤 3.1 环境准备 3.3 修改Redis 配置文件(Master节点操作) 3.4 修改Redis 配置文件(Slave节点操作) 3.5 验证主从效果 二、哨兵 1、哨兵模式原理 2、哨兵模式…...
【Ajax】笔记-原生jsonp跨域请求案例
原生jsonp跨域请求 输入框:输入后,鼠标移开向服务端发送请求,返回用户不存在(直接返回不存在,不做判断) JS <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><me…...
QT--day2(信号与槽,多界面跳转)
第一个界面头文件: #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QIcon> //图标头文件 #include <QPushButton> //按钮类头文件QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public…...
热备份路由协议原理
热备份路由协议原理 HSRP协议/VRRP协议热备份协议 热备份协议(Hot Standby Protocol) 是一种基于冗余设计的协议,用于提高网络的可靠性和冗余性。它允许多个设备共享同一个IP地址,其中一个设备被选为主设备,其他设备…...
模拟实现定时器
关于java标准库中的定时器的使用可以看定时器Timer的使用 大致思路 定义一个MyTimeTask类,该类用于组织要执行任务的内容以及执行任务的时间戳,后面要根据当前系统时间以及执行任务的时间戳进行比较,来判断是否要执行任务或是要等待任务 用一…...
TCP/IP的分包粘包
TCP/IP的分包粘包 分包粘包介绍导致分包粘包的原因导致TCP粘包的原因:导致TCP分包的原因:避免分包粘包的措施 分包粘包介绍 因为TCP为了减少额外开销,采取的是流式传输,所以接收端在一次接收的时候有可能一次接收多个包。而TCP粘…...
盘点:查快递教程
在“寄快递”成为常态的当下,如何快速进行物流信息查询,是收寄人所关心的问题。在回答这个问题之前,首先我们要知道,物流信息查询,有哪些方法? 1、官网单号查询 知道物流公司和单号的情况下,直…...
TransGPT 开源交通大模型开源
TransGPT 是开源交通大模型,主要致力于在真实交通行业中发挥实际价值。 它能够实现交通情况预测、智能咨询助手、公共交通服务、交通规划设计、交通安全教育、协助管理、交通事故报告和分析、自动驾驶辅助系统等功能。 TransGPT 作为一个通用常识交通大模型&#…...
gitignore文件使用方法(gitignore教程)(git status --ignored)(git check-ignore -v <file>)
文章目录 Gitignore文件使用描述Gitignore基本语法1. 基本语法★★★★★2. 配置方法 匹配示例示例1示例2示例3 其他命令git status --ignored(用于显示被Git忽略的文件和文件夹的状态)git check-ignore -v <file>(用于检查指定文件是否…...
mybatis拼接sql导致的oom报错 GC报错
报错1:mybatis拼接过多 java.lang.OutOfMemoryError: GC overhead limit exceeded 具体报错: nested exception is org.apache.ibatis.builder.BuilderException: Error evaluating expression ew.sqlSegment ! null and ew.sqlSegment ! and ew.non…...
如何通俗理解扩散模型?
扩散模型(Diffusion Model)是一类十分先进的基于扩散思想的深度学习生 成模型。生成模型除了扩散模型之外,还有出现较早的 VAE ( Variational Auto- Encoder,变分自编码器) 和 GAN ( Generative Adversarial Net ,生成对抗网络) 等。 虽然它们…...
【C#】并行编程实战:并行编程中的模式
本章将介绍并行编程模式,重点是理解并行代码问题场景并使用并行编程/异步技术解决他们。本章会介绍几种最重要的编程模式。 本教程学习工程:魔术师Dix / HandsOnParallelProgramming GitCode 1、MapReduce 模式 引入 MapReduce 是为了解决处理大数据的问…...
Apache Kafka 入门教程
Apache Kafka 入门教程 一、简介简介架构 二、Kafka 安装和配置JDK安装 Kafka配置文件详解 三、Kafka 的基本操作启动和关闭Topic 创建和删除Partitions 和 Replication 配置Producer 和 Consumer 使用方法ProducerConsumer 四、Kafka 高级应用消息的可靠性保证Kafka StreamKaf…...
python皮卡丘编程代码教程,用python打印皮卡丘
大家好,小编来为大家解答以下问题,如何用print函数打印一只皮卡丘,用python如何打印丘比特之心,现在让我们一起来看看吧!...
shell脚本:数据库的分库分表
#!/bin/bash ######################### #File name:db_fen.sh #Version:v1.0 #Email:admintest.com #Created time:2023-07-29 09:18:52 #Description: ########################## MySQL连接信息 db_user"root" db_password"RedHat123" db_cmd"-u${…...
AtCoder Beginner Contest 312(A~D)
A //语法题也要更仔细嘞,要不然也会wa #include <bits/stdc.h> // #pragma GCC optimize(3,"Ofast","inline") // #pragma GCC optimize(2) using namespace std; typedef long long LL; #define int LL typedef pair<int, int> …...
SQL中Partition的相关用法
使用Partition可以根据指定的列或表达式将数据分成多个分区。每个分区都是逻辑上独立的,可以单独进行查询、插入、更新和删除操作。Partition可以提高查询性能,因为它可以限制在特定分区上执行查询,而不是在整个表上执行。 在SQL中ÿ…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
