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

【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 <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

【跟踪】:

进阶: 是否可以使用 O(1) 空间解决此题?

【相关题目】:

注意: 本题与主站 142. 环形链表 II 题目相同。

2. 题解

2.1 原书题解(快慢指针)-- O(n)

时间复杂度O(n),空间复杂度O(1)
整个流程分三步:

  1. 判断该链表是否有环;
  2. 如果有环,确定环的长度;
  3. 根据环长设置快慢指针的起始位置,移动快慢指针找到入口节点。
/*** 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

题目链接&#xff1a;https://leetcode.cn/problems/c32eOV/ 1. 题目介绍&#xff08;23. 链表中环的入口节点&#xff09; 给定一个链表&#xff0c;返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环&#x…...

LeetCode-96. 不同的二叉搜索树

题目来源 96. 不同的二叉搜索树 递归 1.我们要知道二叉搜索树的性质&#xff0c;对于一个二叉搜索树&#xff0c;其 【左边的节点值 < 中间的节点值 < 右边的节点值】&#xff0c;也就是说&#xff0c;对于一个二叉搜索树&#xff0c;其中序遍历之后形成的数组应该是一…...

JavaWeb基础

Servlet 是在服务器上运行的小程序。这个词是在 Java applet的环境中创造的&#xff0c;Java applet 是一种当作单独文件跟网页一起发送的小程序&#xff0c;它通常用于在客户端运行&#xff0c;结果得到为用户进行运算或者根据用户互作用定位图形等服务。服务器上需要一些程序…...

C++基础了解-03-C++变量类型

C变量类型 一、变量类型 变量其实只不过是程序可操作的存储区的名称。C 中每个变量都有指定的类型&#xff0c;类型决定了变量存储的大小和布局&#xff0c;该范围内的值都可以存储在内存中&#xff0c;运算符可应用于变量上。 变量的名称可以由字母、数字和下划线字符组成。…...

树莓派4b——通过mjpg-streamer使用摄像头

参考博文&#xff1a;(51条消息) 树莓派4b如何打开摄像头_树莓派打开摄像头_会飞的小东的博客-CSDN博客(51条消息) 树莓派4B &#xff08;系统版本11&#xff0c;bullseye&#xff09;更换清华源_树莓派更换清华源_ASSSSHION的博客-CSDN博客这个坑踩了我一星期&#xff0c;找各…...

MySQL运维篇之读写分离

04、读写分离 4.1、介绍 读写分离&#xff0c;简单地说是把对数据库的读和写操作分开&#xff0c;以对应不同的数据库服务器。主数据库提供写操作&#xff0c;从数据库提供读操作&#xff0c;这样能有效地减轻单台数据库的压力。 通过Mycat即可轻易实现上述功能&#xff0c;…...

windows程序最小化到托盘并显示提示信息

windows程序最小化到托盘并显示提示信息背景干货直接上代码解析控制窗口显示初始化托盘添加第一条消息更新界面结束啦背景 有些时候需要程序在最小化的时候可以看到程序进度&#xff0c;甚至需要完全关闭界面&#xff0c;只留下托盘显示&#xff0c;这篇文章就是在这个背景下诞…...

使字符串平衡的最少删除次数(简单动态规划)

给你一个字符串 s &#xff0c;它仅包含字符 a 和 b​​​​ 。 你可以删除 s 中任意数目的字符&#xff0c;使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j &#xff0c;且 s[i] b 的同时 s[j] a&#xff0c;此时认为 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&#xff0c;执行以下命令即可全量构建&#xff0c;并且构建结果只包含linux平台的&#xff1a; KUBE_BUILD_PLATFORMSlinux/amd64 make all GOFLAGS…...

筑基九层 —— 指针详解

目录 前言&#xff1a; 指针详解 前言&#xff1a; 1.CSDN由于我的排版不怎么好看&#xff0c;我的有道云笔记比较美观&#xff0c;请移步有道云笔记 2.修炼必备 1&#xff09;入门必备&#xff1a;VS2019社区版&#xff0c;下载地址&#xff1a;Visual Studio 较旧的下载 -…...

内存清理、动画制作、CPU检测等五款实用软件推荐

人类与99%的动物之间最大差别在于是否会运用工具&#xff0c;借助好的工具&#xff0c;能提升几倍的工作效率。 1.内存清理软件——MemReduct MemReduct是一款内存清理软件&#xff0c;现在越来越多的软件由于硬件的普遍发展&#xff0c;对内存的使用都开始肆无忌惮起来&…...

RocketMQ 5.0 学习笔记

1. 需求 背景&#xff1a;业务需要&#xff0c;平台将使用rocketMQ来实现消息的发送与消费&#xff0c;替代redis的消息功能。 需要在搭建好rocketMQ平台后&#xff0c;进行研究和验证。 技术&#xff1a;Springboot RocketMQ5.0 使用场景&#xff1a;签到活动&#xff0c…...

796.子矩阵的和

输入一个 n行 m列的整数矩阵&#xff0c;再输入 q个询问&#xff0c;每个询问包含四个整数 x1,y1,x2,y2&#xff0c;表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式 第一行包含三个整数 n&#xff0c;m&#xff0c;q。 接下来 n…...

【PySide6】信号(signal)和槽函数(slot),以及事件过滤器

说明 在PYQT中&#xff0c;父控件可以通过两种方式响应子控件的事件&#xff1a; 通过信号(signal)和槽函数(slot)机制连接子控件和父控件父控件可以通过设置eventFilter()方法来监听响应子控件的事件 一、信号(signal)和槽函数(slot) 示例 在PYQT中&#xff0c;每个组件都…...

canal admin管理端配置(二)

下载安装 下载地址&#xff1a; 下载解压即可 配置 修改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的生命周期有四个阶段&#xff1a;加载并实例化、初始化、请求处理、销毁。主要涉及到的方法有init、service、doGet、doPost、destory等 加载并实例化 Servlet容器负责加载和实例化Servelt。当Servlet容器启动时&#xff0c;或者在容器检测到需要这个Servlet来响应第一…...

redis集群模式登陆

总结redis单机模式时&#xff0c;登陆redis的命令格式&#xff1a; ./redis-cli -h 地址 -p 端口redis集群模式时&#xff0c;登陆redis的命令格式&#xff1a; ./redis-cli -h 地址 -p 端口 -c举例1&#xff1a;redis单机模式下登陆rootubuntu:/usr/local/redis/redis-7.0.0/b…...

04-useMemo 、React.memo、useCallback

useMemo 、React.memo、useCallback 一、useMemo 基本用法 缓存数据&#xff0c;模拟 Vue 中的计算属性。 同样useMemo跟vue中component一样&#xff0c;也是有缓存的&#xff0c;会将结果缓存下来 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&…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...