当前位置: 首页 > 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&…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...