LeetCode--HOT100题(26)
目录
- 题目描述:142. 环形链表 II(中等)
- 题目接口
- 解题思路
- 代码
- PS:
题目描述:142. 环形链表 II(中等)
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
LeetCode做题链接:LeetCode-环形链表 II
示例 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 或者链表中的一个有效索引
进阶: 你是否可以使用 O(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) {}
}
解题思路
参考题解:环形链表 II(双指针法,清晰图解)
遇到这种环相遇的问题,第一时间就考虑快慢指针的方法,如果没接触过这类问题,可以看我另一篇文章:环形链表
下面思路是在你理解了判断链表中是否有环的问题的基础上来说的
思路:

- 假设有环,环的长度为b,起始位置到环的起点为a,
- slow走1步,fast走2步,第一相遇的时候
f = 2s(slow = s,fast = f),因为fast是slow的两倍嘛 - fast 比 slow多走了 n 个环的长度,所以
f = s + nb(快慢指针都走过前面的a步了,重合时,快指针就比慢指针多走n圈) - 上面两式相减:
s = nb,f = 2nb - 有图可知:走
a+nb步一定是在环入口,有上式可知:第一次相遇时慢指针已经走了nb步 - 我们需要再走慢指针再走
a步就到环入口,而快指针怎么办?答案是置于head位置,也是再走a步就到环入口 - 所以可以一起走
a步,最终快慢指针相等的位置就是环入口位置了
具体步骤:
- 先构建一次相遇,慢指针走一步,快指针走两步,如果有环,最终在环中相遇
- 接着构建第二次相遇,慢指针位置不变,快指针位置置为head(也就是起始位置)
- 然后快慢指针现在都是同时走一步,直到相遇,相遇的位置就是环的起始结点
代码
/*** 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) {if (head == null) {return null;}// 快慢指针都从head开始ListNode slow = head;ListNode fast = head;do {if (fast == null || fast.next == null) {return null;}// 快慢指针的移动slow = slow.next;fast = fast.next.next;} while (slow != fast); // 快慢指针相遇则退出// 将快指针置于head(开头),慢指针不变,还是在环中fast = head;// 快慢指针再次相遇就是环起始节点while (fast != slow) {// 快慢指针的移动,现在都是一格一格移动(快指针不再移动两个格)fast = fast.next;slow = slow.next;}return fast;}
}

PS:
感谢您的阅读!如果您觉得本篇文章对您有所帮助,请给予博主一个赞喔~
相关文章:
LeetCode--HOT100题(26)
目录 题目描述:142. 环形链表 II(中等)题目接口解题思路代码 PS: 题目描述:142. 环形链表 II(中等) 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返…...
HTTP 请求方法详解
HTTP 请求方法详解 请求方法 请求方法(Request Methods)是在 HTTP 请求中用于指定对目标资源执行的操作类型。每个请求都需要指定一个请求方法,以告知服务器要执行的操作。 以下是一些常见的 HTTP 请求方法及其主要用途: GET&…...
孤立随机森林(Isolation Forest)(Python实现)
目录 1 简介 2 孤立随机森林算法 2.1 算法概述 2.2 原理介绍 2.3 算法步骤 3 参数讲解 4 Python代码实现 5 结果 1 简介 孤立森林(isolation Forest)是一种高效的异常检测算法,它和随机森林类似,但每次选择划分属性和划…...
小程序如何自定义分享内容
小程序项目中遇到门票转增功能,用户可将自己购买的门票分享给好友,好友成功领取即得门票一张 1.自定义分享按钮 通过button里的open-type属性里的share参数即自可定义分享按钮 <button open-type"share">分享</button>2.配置分…...
SpringBoot整合WebSocket详解
环境:Springboot3.0.5 WebSocket介绍 WebSocket协议RFC 6455提供了一种标准化的方式,通过一个TCP连接在客户端和服务器之间建立全双工、双向的通信通道。它是一个不同于HTTP的TCP协议,但设计为在HTTP之上工作,使用80和443端口&am…...
伪原创神码ai怎么样【php源码】
这篇文章主要介绍了python汉化补丁包下载,具有一定借鉴价值,需要的朋友可以参考下。希望大家阅读完这篇文章后大有收获,下面让小编带着大家一起了解一下。 火车头采集ai伪原创插件截图: ** Spyder汉化(python汉化&…...
Air001基于Keil环境开发,使用airisp串口命令行烧录
Air001基于Keil环境开发,使用airisp串口命令行烧录 有人会有这样的疑惑,使用Keil平台开发,为什么不直接使用CMSIS-DAP直接烧录,还要使用串口方式来去单独烧录,不是我不想,目前使用合宙官方的Air103芯片版本…...
kubernetes 中的事件(event)简介以及如何收集event和基于event告警
引用另外一篇文章对k8s event的介绍 1.什么是kubernetes事件 Kubernetes Events 是一种 Kubernetes 资源对象,记录了某个组件在某个时间做了某个动作,用于展示集群内发生的情况,当 Kubernetes 集群中资源状态发生变化时,可以产生…...
C++小游戏贪吃蛇源码
graphics.h是针对DOS下的一个C语言图形库 (c也可以) 目前支持下载此头文件的常用的有两种: 1. EGE (Easy Graphics Engine)2. EasyX Graphics LibraryEGE, 全名Easy Graphics Engine, 是windows下的简易绘图库,是一个类似BGI(graphics.h)的面向C/C语言新手的图形库…...
【密码学】穴居人密码
穴居人密码 文字记载中,有时会把来自古希腊文化之前的各种记录作为密码学的例子,但称它们为密码学一定太不严格了,这是因为那些方法都太原始了。密码学的起源能追溯到多早,取决于你把密码学的相关定义确定得有多宽泛。大多数作者都…...
neo4j的CQL命令实例演示
天行健,君子以自强不息;地势坤,君子以厚德载物。 每个人都有惰性,但不断学习是好好生活的根本,共勉! 文章均为学习整理笔记,分享记录为主,如有错误请指正,共同学习进步。…...
vue3+ts使用antv/x6
使用 2.x 版本 x6.antv 新官网: 安装 npm install antv/x6 //"antv/x6": "^2.1.6",项目结构 1、初始化画布 index.vue <template><div id"container"></div> </template><script setup langts> import { onM…...
wsl1 ubuntu通过宿主机代理连接外网
文章目录 环境变量配置apt换源apt安装,测试是否能通外网可能出现的问题:Temporary failure resolving 参考 背景:公司电脑是局域网,通过走代理来连接外网 wsl1 ubuntu想要通过来连接宿主机的局域网代理,访问外网 可以…...
ubuntu20.04 opencv4.2 安装笔记
参考: https://docs.opencv.org/4.x/d7/d9f/tutorial_linux_install.html Build with opencv_contrib # 1. Install minimal prerequisites, libgtk2.0-dev pkg-config 用来显示图像 sudo apt update && sudo apt install -y cmake g wget un…...
ubuntu安装nginx以及php的部署
目录 1.安装依赖包 2.安装nginx 3.编译nginx 4.启动nginx 5.访问nginx 6.增加源地址 7.安装php 8.配置php-fpm 9.修改权限 10.配置nginx里的php 11.启动php-fpm 12.配置php文件以及权限 13.登陆查看 1.安装依赖包 apt-get install gcc apt-get install libpcre3 l…...
IntelliJ IDEA 2021/2022关闭双击shift全局搜索
我这里演示的是修改,删除是右键的时候选择Remove就好了 IDEA左上角 File-->Settings 找到Navigate -->Search Everywhere ,右键添加快捷键。 OK --> Apply应用...
HTML 元素中的name 属性
name 属性是 HTML 元素中常用的属性之一。它用于指定表单元素的名称,以便在提交表单时将其值与对应的键关联起来。 每个表单元素(例如 <input>、<select> 和 <textarea>)都可以具有一个 name 属性,该属性为元素…...
快速上手React:从概述到组件与事件处理
前言 「作者主页」:雪碧有白泡泡 「个人网站」:雪碧的个人网站 「推荐专栏」: ★java一站式服务 ★ ★ React从入门到精通★ ★前端炫酷代码分享 ★ ★ 从0到英雄,vue成神之路★ ★ uniapp-从构建到提升★ ★ 从0到英雄ÿ…...
K8S系列文章之 离线安装自动化工具Ansible
参考 文档 离线安装 Ansible - DevOps - dbaselife 一、Ansible简介 Ansible是一款开源的IT配置管理工具,常被IT界的小伙伴们用于自动化的场景,多用在服务部署、配置管理方面。配置文件采用最常见的yaml格式,学习起来也是比较容易ÿ…...
mysql8.0.3集群搭建
下载mysql安装包: https://dev.mysql.com/downloads/mysql/5.7.html#downloads 准备环境 1、准备三台服务器并设置hosts 192.168.236.143 mysql1 192.168.236.144 mysql2 192.168.236.145 mysql32、设置免密登陆 #生成秘钥 ssh-keygen -t rsa #一直按Enter即可…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
算术操作符与类型转换:从基础到精通
目录 前言:从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符:、-、*、/、% 赋值操作符:和复合赋值 单⽬操作符:、--、、- 前言:从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...
规则与人性的天平——由高考迟到事件引发的思考
当那位身着校服的考生在考场关闭1分钟后狂奔而至,他涨红的脸上写满绝望。铁门内秒针划过的弧度,成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定",构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...
小智AI+MCP
什么是小智AI和MCP 如果还不清楚的先看往期文章 手搓小智AI聊天机器人 MCP 深度解析:AI 的USB接口 如何使用小智MCP 1.刷支持mcp的小智固件 2.下载官方MCP的示例代码 Github:https://github.com/78/mcp-calculator 安这个步骤执行 其中MCP_ENDPOI…...
13.10 LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析
LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析 LanguageMentor 对话式训练系统架构与实现 关键词:多轮对话系统设计、场景化提示工程、情感识别优化、LangGraph 状态管理、Ollama 私有化部署 1. 对话训练系统技术架构 采用四层架构实现高扩展性的对话训练…...
李沐--动手学深度学习--GRU
1.GRU从零开始实现 #9.1.2GRU从零开始实现 import torch from torch import nn from d2l import torch as d2l#首先读取 8.5节中使用的时间机器数据集 batch_size,num_steps 32,35 train_iter,vocab d2l.load_data_time_machine(batch_size,num_steps) #初始化模型参数 def …...
深度解析云存储:概念、架构与应用实践
在数据爆炸式增长的时代,传统本地存储因容量限制、管理复杂等问题,已难以满足企业和个人的需求。云存储凭借灵活扩展、便捷访问等特性,成为数据存储领域的主流解决方案。从个人照片备份到企业核心数据管理,云存储正重塑数据存储与…...
Linux中INADDR_ANY详解
在Linux网络编程中,INADDR_ANY 是一个特殊的IPv4地址常量(定义在 <netinet/in.h> 头文件中),用于表示绑定到所有可用网络接口的地址。它是服务器程序中的常见用法,允许套接字监听所有本地IP地址上的连接请求。 关…...
