Leetcode42-环形链表

题目

给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1:
在这里插入图片描述
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

代码

static public ListNode hasCycle_StartNode(ListNode head) {
    ListNode slow = head, fast = head; // 将 fast 的起始位置设置为 head
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {// 此时slow和fast在环的中相遇,但是相遇的点不一定是环的入口点,因为进入指针环的时机是不一样的
            ListNode cycle = head;// 重置一个新节点,走a的距离,就可以和slow后续的移动汇合,且一定是环开始的节点
            while (cycle != slow) {
                cycle = cycle.next;
                slow = slow.next;
            }
            return cycle;
        }
    }
    return null;
}

总结

a:从链表头到环的起始节点的距离。
b:从环的起始节点到快慢指针相遇点的距离。
c:环的长度。

慢指针 slow 从头节点开始,走了 a + b 的距离到达相遇点。
快指针 fast 从头节点开始,走了 a + b + n*c 的距离(其中 n 是快指针在环内绕的圈数)。
当快慢指针相遇时,有以下关系:

  • slow 走的距离:a + b
  • fast 走的距离:a + b + n*c

由于快指针的速度是慢指针的两倍,得出: 2(a + b) = a + b + nc => a + b = nc
这表明慢指针走的距离a+b是环长度的整数倍

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/937317.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

计算机网络错题

文章目录 码分复用透明传输差错检测停止-等待协议回退N帧协议CSMA/CD协议以太网交换机Vlanip地址的无分类编制方法ip地址的应用规划ip数据包的发送和转发过程路由信息协议IPI2016201720202022 2.5信道 码分复用 透明传输 差错检测 停止-等待协议 回退N帧协议 CSMA/CD协议 以太网…

改进系列(5):在ResNet网络添加SelfAttention自注意力层实现的遥感卫星下的土地利用情况图像分类

目录 1. ResNet介绍 2. SelfAttention 层 3. ResNet34 SelfAttention 4. 遥感卫星下的土地使用情况分类 4.1 土地使用情况数据集 4.2 训练 4.3 训练结果 4.4 推理 1. ResNet介绍 ResNet(残差网络)是一种深度卷积神经网络模型,由Ka…

ARM循环程序和子程序设计

1、计算下列两组数据的累加和并存入到sum1和 sum2 单元中。datal:0x12,0x935,0x17,0x100,0x95,0x345。 data2:0x357,0x778,0x129,0x188,0x190,0x155,0x167。 1.定义数据段 ;定义数据段,类型为data(表示为数据段),权限为可读可写(程序可以读取和修改这…

蓝桥杯刷题——day5

蓝桥杯刷题——day5 题目一题干解题思路一代码解题思路二代码 题目二题干解题思路代码 题目一 题干 给定n个整数 a1,a2,⋯ ,an,求它们两两相乘再相加的和,即: 示例一: 输入: 4 1 3 6 9 输出: 117 题目链…

1_linux系统网络性能如何优化——几种开源网络协议栈比较

之前合集《计算机网络从入门到放弃》第一阶段算是已经完成了。都是理论,没有实操,让“程序猿”很难受,操作性不如 Modbus发送的报文何时等到应答和 tcp通信测试报告单1——connect和send。开始是想看linux内核网络协议栈的源码,然…

opencv——识别图片颜色并绘制轮廓

图像边缘检测 本实验要用到Canny算法,Canny边缘检测方法常被誉为边缘检测的最优方法。 首先,Canny算法的输入端应为图像的二值化结果,接收到二值化图像后,需要按照如下步骤进行: 高斯滤波。计算图像的梯度和方向。非极…

Edge SCDN深度解析,边缘安全加速的创新实践

边缘安全加速(Edge Secure Content Delivery Network,SCDN)是酷盾安全推出的边缘集分布式 DDoS 防护、CC 防护、WAF 防护、BOT 行为分析为一体的安全加速解决方案。通过边缘缓存技术,智能调度使用户就近获取所需内容,为…

软考高级架构 —— 10.6 大型网站系统架构演化实例 + 软件架构维护

10.6 大型网站系统架构演化实例 大型网站的技术挑战主要来自于庞大的用户,高并发的访问和海量的数据,主要解决这类问题。 1. 单体架构 特点: 所有资源(应用程序、数据库、文件)集中在一台服务器上。适用场景: 小型网站&am…

Golang囊地鼠gopher

开发知识点-golang 介绍红队专题-Golang工具Fscan简介主要功能ubuntu 安装windows 安装常用命令:项目框架源文件common目录Plugins目录Webscan目录入口点插件扫描类型爆破插件common.ScantypeWebtitle函数webpoc扫描POC 执行CEL-GO 实践CEL指纹识别免杀源码特征参考链接红队专…

多分类交叉熵与稀疏分类交叉熵

总结: 标签为 One-hot 编码的多分类问题,用分类交叉熵对于标签为整数的多分类问题,用稀疏分类交叉熵稀疏分类交叉熵内部会将整数标签转换为 One-hot 编码,而如果标签已经是 One-hot 编码的形式,再使用稀疏分类交叉熵就会多此一举。 算例 假设我们有三个类别:A、B 和 C。…

360极速浏览器不支持看PDF

360安全浏览器采用的是基于IE内核和Chrome内核的双核浏览器。360极速浏览器是源自Chromium开源项目的浏览器,不但完美融合了IE内核引擎,而且实现了双核引擎的无缝切换。因此在速度上,360极速浏览器的极速体验感更佳。 展示自己的时候要在有优…

零基础微信小程序开发——小程序的宿主环境(保姆级教程+超详细)

🎥 作者简介: CSDN\阿里云\腾讯云\华为云开发社区优质创作者,专注分享大数据、Python、数据库、人工智能等领域的优质内容 🌸个人主页: 长风清留杨的博客 🍃形式准则: 无论成就大小,…

麒麟信安推出支持信创PC的新一代云桌面方案,助力政务信创高效安全运维

12月11日,在第二届国家新一代自主安全计算系统产业集群融通生态大会上,麒麟信安发布了支持信创PC的新一代云桌面方案,该方案是基于国际TCI架构实现国产PC机云化纳管在国内的首次发布,并与银河麒麟桌面操作系统、长城国产PC整机实现…

vim优化

1.编辑如下内容&#xff1a; cat > /root/.vimrc <<EOF set tabstop2 " 设置 Tab 为 2 个空格 set shiftwidth2 " 设置自动缩进为 2 个空格 set expandtab " 将 Tab 转换为空格 " 基本设置 set number syntax on" 快捷键设置…

hive—常用的日期函数

目录 1、current_date 当前日期 2、now() 或 current_timestamp() 当前时间 3、datediff(endDate, startDate) 计算日期相差天数 4、months_between(endDate, startDate) 日期相差月数 5、date_add(startDate, numDays) 日期加N天 6、date_sub(startDate, numDays) 日期减…

医学分割数据集肾结石分割数据集labelme格式359张1类别

数据集格式&#xff1a;labelme格式(不包含mask文件&#xff0c;仅仅包含jpg图片和对应的json文件) 图片数量(jpg文件个数)&#xff1a;359 标注数量(json文件个数)&#xff1a;359 标注类别数&#xff1a;1 标注类别名称:["kidney stone"] 每个类别标注的框数&…

Vulnstack红日安全内网域渗透靶场2实战攻略

一&#xff1a;环境搭建 新增的网卡VMnet2&#xff0c;ip调成10段。 PC配置如下&#xff1a; DC在该环境中充当是域控。DC配置如下 &#xff1a; WEB配置&#xff1a;需要两块网卡&#xff0c;相当于网关服务器。 作者把外网网段都写成了192.168.111.1/24&#xff0c;我们可以…

基础库urllib的使用

学习爬虫&#xff0c;其基本的操作便是模拟浏览器向服务器发出请求&#xff0c;那么我们需要从哪个地方做起呢?请求需要我们自己构造吗?我们需要关心请求这个数据结构怎么实现吗?需要了解 HTTP、TCP、IP层的网络传输通信吗?需要知道服务器如何响应以及响应的原理吗? 可能…

【大数据技术基础】【记录Ubuntu 16.04升级到18.04】Ubuntu的一个版本升级到另一个版本

在 Ubuntu 操作系统中进行软件更新和系统升级 Ubuntu Kylin 16.04 LTS 系统进行系统升级到 Ubuntu 18.04.6 LTS 版本 升级提示&#xff1a;系统弹出提示框&#xff0c;告知用户有新版本的 Ubuntu 可用&#xff0c;询问用户是否想要升级。 认证窗口&#xff1a;显示了一个认证…

【环境搭建】Python、PyTorch与cuda的版本对应表

一个愿意伫立在巨人肩膀上的农民...... 在深度学习的世界里&#xff0c;选择合适的工具版本是项目成功的关键。CUDA、PyTorch和Python作为深度学习的三大支柱&#xff0c;它们的版本匹配问题不容忽视。错误的版本组合可能导致兼容性问题、性能下降甚至项目失败。因此&#xff0…