【LeetCode】剑指 Offer 23. 链表中环的入口节点 p139 -- Java Version
题目链接:https://leetcode.cn/problems/c32eOV/
1. 题目介绍(23. 链表中环的入口节点)
给定一个链表,返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数
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或者链表中的一个有效索引
【跟踪】:
进阶: 是否可以使用 O(1) 空间解决此题?
【相关题目】:
注意: 本题与主站 142. 环形链表 II 题目相同。
2. 题解
2.1 原书题解(快慢指针)-- O(n)
时间复杂度O(n),空间复杂度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) {ListNode meetingNode = meetingNode(head);// 该链表无环,返回nullif (meetingNode == null) return null;// 链表有环,从相遇点开始计数,直到再次到达相遇点ListNode fast = meetingNode;int cycleLength = 1;while (fast.next != meetingNode){fast = fast.next;cycleLength++;}System.out.println(cycleLength);// 快指针返回head,并前进环长步数fast = head;for (int i = 0; i < cycleLength; i++){fast = fast.next;}// 快慢指针开始移动,每次移动一步,相遇节点即为入口节点ListNode slow = head;while (fast != slow){fast = fast.next;slow = slow.next;}return fast;}public ListNode meetingNode(ListNode head){// 判断头节点是否为空if (head == null) return null;// 定义快慢指针ListNode slow = head.next;if (slow == null) return null;ListNode fast = slow.next;while (fast != null && slow != null){if (fast == slow) return fast;// 慢指针每次走一步,快指针每次走两步slow = slow.next;fast = fast.next;if (fast != null) fast = fast.next;}return null;}
}

2.2 快慢指针简化版 – O(n)
时间复杂度O(n),空间复杂度O(1)

思路基本和2.1一致,不同的是这里简化了求环长,直接让fast回到了头节点

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head, slow = head;while (true) {if (fast == null || fast.next == null) return null;fast = fast.next.next;slow = slow.next;if (fast == slow) break;}fast = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return fast;}
}

3. 参考资料
[1] 剑指 Offer II 022. 链表中环的入口节点(双指针,清晰图解)-- 2.2 题解参考
相关文章:
【LeetCode】剑指 Offer 23. 链表中环的入口节点 p139 -- Java Version
题目链接:https://leetcode.cn/problems/c32eOV/ 1. 题目介绍(23. 链表中环的入口节点) 给定一个链表,返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环&#x…...
LeetCode-96. 不同的二叉搜索树
题目来源 96. 不同的二叉搜索树 递归 1.我们要知道二叉搜索树的性质,对于一个二叉搜索树,其 【左边的节点值 < 中间的节点值 < 右边的节点值】,也就是说,对于一个二叉搜索树,其中序遍历之后形成的数组应该是一…...
JavaWeb基础
Servlet 是在服务器上运行的小程序。这个词是在 Java applet的环境中创造的,Java applet 是一种当作单独文件跟网页一起发送的小程序,它通常用于在客户端运行,结果得到为用户进行运算或者根据用户互作用定位图形等服务。服务器上需要一些程序…...
C++基础了解-03-C++变量类型
C变量类型 一、变量类型 变量其实只不过是程序可操作的存储区的名称。C 中每个变量都有指定的类型,类型决定了变量存储的大小和布局,该范围内的值都可以存储在内存中,运算符可应用于变量上。 变量的名称可以由字母、数字和下划线字符组成。…...
树莓派4b——通过mjpg-streamer使用摄像头
参考博文:(51条消息) 树莓派4b如何打开摄像头_树莓派打开摄像头_会飞的小东的博客-CSDN博客(51条消息) 树莓派4B (系统版本11,bullseye)更换清华源_树莓派更换清华源_ASSSSHION的博客-CSDN博客这个坑踩了我一星期,找各…...
MySQL运维篇之读写分离
04、读写分离 4.1、介绍 读写分离,简单地说是把对数据库的读和写操作分开,以对应不同的数据库服务器。主数据库提供写操作,从数据库提供读操作,这样能有效地减轻单台数据库的压力。 通过Mycat即可轻易实现上述功能,…...
windows程序最小化到托盘并显示提示信息
windows程序最小化到托盘并显示提示信息背景干货直接上代码解析控制窗口显示初始化托盘添加第一条消息更新界面结束啦背景 有些时候需要程序在最小化的时候可以看到程序进度,甚至需要完全关闭界面,只留下托盘显示,这篇文章就是在这个背景下诞…...
使字符串平衡的最少删除次数(简单动态规划)
给你一个字符串 s ,它仅包含字符 a 和 b 。 你可以删除 s 中任意数目的字符,使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ,且 s[i] b 的同时 s[j] a,此时认为 s 是 平衡 的。 请你返回使 s 平衡 的 最少 删除次…...
linux网络广播使用
广播使用的特殊的IP地址: 最后一位是255时的IP地址是给广播预留的IP地址, 如:192.168.1.255 UDP服务器在广播数据时,数据报使用的地址不是UDP服务器地址,而是广播地址 如:UDP服务器地址是:192.168.1.110 UDP服务器广播数据时使用地址是:192.168.1.255 UDP数据包发送给交换机…...
Kubernetes源码学习
kubernetes源码剖析 1.下载和编译源码 go 1.18.3 kubernetes 1.24.2 centos 7.9 进入目录$GOPATH/src/k8s.io/kubernetes,执行以下命令即可全量构建,并且构建结果只包含linux平台的: KUBE_BUILD_PLATFORMSlinux/amd64 make all GOFLAGS…...
筑基九层 —— 指针详解
目录 前言: 指针详解 前言: 1.CSDN由于我的排版不怎么好看,我的有道云笔记比较美观,请移步有道云笔记 2.修炼必备 1)入门必备:VS2019社区版,下载地址:Visual Studio 较旧的下载 -…...
内存清理、动画制作、CPU检测等五款实用软件推荐
人类与99%的动物之间最大差别在于是否会运用工具,借助好的工具,能提升几倍的工作效率。 1.内存清理软件——MemReduct MemReduct是一款内存清理软件,现在越来越多的软件由于硬件的普遍发展,对内存的使用都开始肆无忌惮起来&…...
RocketMQ 5.0 学习笔记
1. 需求 背景:业务需要,平台将使用rocketMQ来实现消息的发送与消费,替代redis的消息功能。 需要在搭建好rocketMQ平台后,进行研究和验证。 技术:Springboot RocketMQ5.0 使用场景:签到活动,…...
796.子矩阵的和
输入一个 n行 m列的整数矩阵,再输入 q个询问,每个询问包含四个整数 x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式 第一行包含三个整数 n,m,q。 接下来 n…...
【PySide6】信号(signal)和槽函数(slot),以及事件过滤器
说明 在PYQT中,父控件可以通过两种方式响应子控件的事件: 通过信号(signal)和槽函数(slot)机制连接子控件和父控件父控件可以通过设置eventFilter()方法来监听响应子控件的事件 一、信号(signal)和槽函数(slot) 示例 在PYQT中,每个组件都…...
canal admin管理端配置(二)
下载安装 下载地址: 下载解压即可 配置 修改canal.admin-1.1.5\conf\application.yml server:port: 8089 #端口根据是否冲突修改 spring:jackson:date-format: yyyy-MM-dd HH:mm:sstime-zone: GMT8spring.datasource:address: 192.0.16.12:3306#数据库ip和端口…...
Servlet 生命周期
Servlet的生命周期有四个阶段:加载并实例化、初始化、请求处理、销毁。主要涉及到的方法有init、service、doGet、doPost、destory等 加载并实例化 Servlet容器负责加载和实例化Servelt。当Servlet容器启动时,或者在容器检测到需要这个Servlet来响应第一…...
redis集群模式登陆
总结redis单机模式时,登陆redis的命令格式: ./redis-cli -h 地址 -p 端口redis集群模式时,登陆redis的命令格式: ./redis-cli -h 地址 -p 端口 -c举例1:redis单机模式下登陆rootubuntu:/usr/local/redis/redis-7.0.0/b…...
04-useMemo 、React.memo、useCallback
useMemo 、React.memo、useCallback 一、useMemo 基本用法 缓存数据,模拟 Vue 中的计算属性。 同样useMemo跟vue中component一样,也是有缓存的,会将结果缓存下来 import React, { useMemo, useState } from react;export default functio…...
windows下安装emqx Unable to load emulator DLL@if ===/ SET data_dir=“
1.报错内容 I:\0-software\02-emqx\emqx-5.0.19-windows-amd64\bin>emqx start Unable to load emulator DLL (I:\0-software\02-emqx\emqx-5.0.19-windows-amd64\erts-12.3.2.9\bin\beam.smp.dll) 此时不应有 SET。 I:\0-software\02-emqx\emqx-5.0.19-windows-amd64\bin&…...
模型timm/ViT-B-16-SigLIP简要介绍及其应用场景
目录一、timm/ViT-B-16-SigLIP 是什么模型二、模型结构(核心架构)1️⃣ 图像编码器2️⃣ 文本编码器3️⃣ 对齐训练三、为什么叫 ViT-B-16四、在 timm 中如何使用五、典型应用场景1️⃣ Zero-shot 图像分类2️⃣ 图文检索(Image-Text Retriev…...
突破数字阅读壁垒:bypass-paywalls-chrome-clean工具深度实战指南
突破数字阅读壁垒:bypass-paywalls-chrome-clean工具深度实战指南 【免费下载链接】bypass-paywalls-chrome-clean 项目地址: https://gitcode.com/GitHub_Trending/by/bypass-paywalls-chrome-clean 在信息获取成本日益增高的今天,优质内容常常…...
工单系统已经上线,但 IT 管理并没有真正变好
在很多企业中,引入 IT 工单系统往往被视为 IT 管理升级的重要一步。 有了统一入口、有了记录机制、有了流程流转,看起来一切都开始变得规范起来。但实际运行一段时间后,不少团队会发现: 工单确实在增加,流程也在走&…...
Element React深度解析:企业级React组件库的架构设计与实战应用
Element React深度解析:企业级React组件库的架构设计与实战应用 【免费下载链接】element-react Element UI 项目地址: https://gitcode.com/gh_mirrors/el/element-react Element React是一款基于React框架构建的企业级UI组件库,它为开发者提供了…...
5分钟解决经典游戏兼容性问题:DDrawCompat完整使用指南
5分钟解决经典游戏兼容性问题:DDrawCompat完整使用指南 【免费下载链接】DDrawCompat DirectDraw and Direct3D 1-7 compatibility, performance and visual enhancements for Windows Vista, 7, 8, 10 and 11 项目地址: https://gitcode.com/gh_mirrors/dd/DDraw…...
华硕笔记本性能困境突破:G-Helper工具的全方位优化方案
华硕笔记本性能困境突破:G-Helper工具的全方位优化方案 【免费下载链接】g-helper Lightweight Armoury Crate alternative for Asus laptops. Control tool for ROG Zephyrus G14, G15, G16, M16, Flow X13, Flow X16, TUF, Strix, Scar and other models 项目地…...
告别裸机!用状态机思路重构你的51单片机温度监测程序(以DS18B20为例)
告别裸机!用状态机思路重构你的51单片机温度监测程序(以DS18B20为例) 在嵌入式开发中,51单片机因其简单易用、成本低廉而广受欢迎。但当项目复杂度上升时,传统的"while循环延时"式代码往往会陷入维护噩梦——…...
ollama-QwQ-32B量化部署:在4GB内存设备运行OpenClaw的配置
ollama-QwQ-32B量化部署:在4GB内存设备运行OpenClaw的配置 1. 为什么要在低配设备上折腾大模型? 去年冬天,我在树莓派上第一次尝试部署OpenClaw时,被现实狠狠教育了一顿——32GB内存的笔记本跑得飞起,换到4GB的树莓派…...
3步搞定Windows 11优化:用Win11Debloat让你的电脑更快更干净
3步搞定Windows 11优化:用Win11Debloat让你的电脑更快更干净 【免费下载链接】Win11Debloat 一个简单的PowerShell脚本,用于从Windows中移除预装的无用软件,禁用遥测,从Windows搜索中移除Bing,以及执行各种其他更改以简…...
Termius vs SecureCRT:为什么这款内置FTP的SSH工具更适合中文用户?
Termius vs SecureCRT:为什么这款内置FTP的SSH工具更适合中文用户? 作为开发者,每天与服务器打交道是家常便饭。选择一款趁手的SSH工具,就像程序员挑选键盘一样重要——不仅要功能强大,更要符合个人使用习惯。对于中文…...
