【数据结构与算法】力扣 142. 环形链表 II

题目描述

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

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 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 或者链表中的一个有效索引

分析解答

以下分析和图解部分来自代码随想录

这道题有两个关键点:

  1. 是否有环
  2. 有环需要找到环的入口

是否有环

有环需要使用双指针(快慢指针)来判断。比如使快指针一次移动两个节点,慢指针一次移动一个节点,当进入环中,慢指针一定会在某个时刻追上快指针。举个例子:

  • 1,2,3,4,5,3,4,5,3,4,5,3,4,5,3,4,5,3,4,5,3,4,5,3,4,5 – 慢
  • 3,5,1,3,5,1,3,5,1,3,5,1,3,5,1,3,5,1,3,5,1,3,5 – 快

image.png

image.png

找出环的出口

第一次接触真的会一脸懵 O.o

image.png

以下两图很好地解释了为什么 slow 只在转第一圈的时候一定会被 fast 追上。

image.png

image.png

所以可以列出等式((n >= 1)):

  • slow = x + y
  • fast = x + y + n(y + z)
  • 2(x + y) = x + y + n(y + z)
  • x + y = n(y + z)
  • x = n(y + z) - y
  • x = (n - 1)(y + z) + z

所以当 n 为 1 的时候, x = z。代表着如果有一个节点在相遇处,一个节点在head处,他们同时出发,刚好会在环形入口节点处相遇。

n 表示相遇的时候,快指针已经在环内转的圈数。

完整代码:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    if(!head || !head.next) return null;
    let fast = head.next.next
    let slow = head.next
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
        if (fast == slow) {
            slow = head
            while (fast != slow) {
                fast = fast.next
                slow = slow.next
            }
            return slow
        }
    }
    return null
};

思路拓展

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

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

相关文章

倒计时 抢登CCF-C NSPW’24论文战场,4月12日截稿,等你来征服

会议之眼 快讯 2024年NSPW&#xff08;The New Security Paradigms Workshop&#xff09;即新安全范式研讨会将于 2024 年 9月16日-18日在美国宾夕法尼亚州贝德福德举行&#xff01;NSPW是一个专注于信息安全领域的年度会议&#xff0c;该会议旨在为那些挑战计算机安全领域主流…

小小算式(1 + 2) * (3 + 4)背后的大道理

目录 前缀表示法&#xff08;波兰表达式&#xff09; 中缀表达法 后缀表达法&#xff08;逆波兰表达式&#xff09; 三种表达法的相互转换 练习&#xff1a;逆波兰表达式求值 前缀表示法&#xff08;波兰表达式&#xff09; 波兰表示法&#xff08;英语&#xff1a;Polis…

第四十七周:文献阅读+AGCN+Wavenet network

目录 摘要 Abstract 文献阅读&#xff1a;结合自适应图卷积和CNN-LSTM的多站点水质预测模型 现有问题 提出方法 方法论 Adaptive graph convolution network&#xff08;自适应图卷积网络&#xff09; WaveNet network&#xff08;WaveNet网络&#xff09; CNN-LSTM混…

php反序列化漏洞——phar反序列化漏洞

一.什么是phar文件 类比java语言 JAR是开发Java程序一个应用&#xff0c;包括所有的可执行、可访问的文件&#xff0c;都打包进了一个JAR文件里使得部署过程十分简单。 PHAR("Php ARchive")是PHP里类似于JAR的一种打包文件 对于PHP 5.3 或更高版本&#xff0c;Ph…

【UE 网络】DS框架学习路线

目录 0 引言1 如何学习DS框架1. 熟悉Unreal Engine基础2. 学习网络编程基础3. 掌握UE网络概念4. 实践和实验5. 加入社区和论坛6. 官方示例和案例研究7. 专业书籍和在线课程 2 DS框架重要知识点有哪些1. 网络复制2. 远程过程调用&#xff08;RPC&#xff09;3. 客户端服务器架构…

0点起C语言

用sizeof()来查看在你的平台上到底占用多少你多少字节的内存。 Int x sizeof(int); Int xsizeof(shrt int); Int xsizeof(long); Int xsizeof(long double); 等等。 http://www.enet.com.cn/article/2012/0822/A20120822153730_2.shtml #—是个预处理的标志&#xff0c;表示对文…

如何本地搭建Discuz论坛并实现无公网IP远程访问

文章目录 前言1.安装基础环境2.一键部署Discuz3.安装cpolar工具4.配置域名访问Discuz5.固定域名公网地址6.配置Discuz论坛 前言 Crossday Discuz! Board&#xff08;以下简称 Discuz!&#xff09;是一套通用的社区论坛软件系统&#xff0c;用户可以在不需要任何编程的基础上&a…

自动化测试的6大适用场景

不能代替手工测试&#xff0c;因为自动化测试有适用场景&#xff1a;自动化测试的6大适用场景 自动化测试可以在短时间内执行大量的测试任务&#xff0c;缩短了测试时间和人工成本&#xff1b;而自动化测试脚本可以重复执行&#xff0c;提高了测试效率&#xff1b;而通过自动化…

【C++】流程控制语句:跳转语句之Break

在C编程语言中&#xff0c;流程控制不仅包括循环和条件分支&#xff0c;还包括一类特别重要的语句——跳转语句。 这类语句允许程序在执行过程中“打破”常规流程&#xff0c;转而执行其他位置的代码。 C提供了四种跳转语句&#xff1a;break、continue、goto 以及 return。…

充电桩项目,开源啦!

好&#xff0c;我是田哥 很多人&#xff0c;最近都在关注我的充电桩项目&#xff0c;之前建了一个微服务架构的项目&#xff0c;也有单体项目的代码开源。 今天&#xff0c;我把最新版微服务架构的充电桩项目源代码开源。 充电桩的输入端与交流电网直接连接&#xff0c;输出端都…

【线段树】【前缀和】:1687从仓库到码头运输箱子

本题简单解法 C前缀和算法的应用&#xff1a;1687从仓库到码头运输箱子 本文涉及的基础知识点 C算法&#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 线段树 LeetCode1687从仓库到码头运输箱子 你有一辆货运卡车&#xff0c;你需要用这一辆车…

【Vue】响应式原理与ref

首先讲讲JS中的Proxy JavaScript 运行环境包含了一些不可枚举、不可写入的对象属性&#xff0c;然而在 ES5 之前开发者无法定义他们自己的不可枚举属性或不可写入属性。ES5 引入 Object.defineProperty() 方法以便开发者在这方面能够像 JS 引擎那样做。 ES6 为了让开发者能进…

阿里云服务器可以干嘛?阿里云服务器八大用途介绍

阿里云服务器可以干嘛&#xff1f;能干啥你还不知道么&#xff01;简单来讲可用来搭建网站、个人博客、企业官网、论坛、电子商务、AI、LLM大语言模型、测试环境等&#xff0c;阿里云百科aliyunbaike.com整理阿里云服务器的用途&#xff1a; 阿里云服务器活动 aliyunbaike.com…

springboot实现上传文件接口(简单版)

使用springboot实现一个最简单版本的上传文件接口 private String uploadPath "C:/imageFiles";RequestMapping(value "/upload", method RequestMethod.POST)private Result upload( RequestParam("modelName") String modelName,RequestPar…

前端实现拖拽div修改宽度,用于菜单栏等多处场景

1、演示 2、 比较简单&#xff0c;直接上源码&#xff08;内部有注释&#xff09; <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-…

鸿蒙内核源码分析 (并发并行篇) | 内核如何管理多个 CPU?

理解并发概念 并发&#xff08;Concurrent&#xff09;: 多个线程在单个核心运行&#xff0c;同一时间只能一个线程运行&#xff0c;内核不停切换线程&#xff0c;看起来像同时运行&#xff0c;实际上是线程被高速的切换. 通俗好理解的比喻就是高速单行道&#xff0c;单行道指…

【canvas】canvas的基础使用(一):创建canvas

canvas Canvas API 提供了一个通过JavaScript 和 HTML的<canvas>元素来绘制图形的方式。它可以用于动画、游戏画面、数据可视化、图片编辑以及实时视频处理等方面。 Canvas API 主要聚焦于 2D 图形。 canvas元素 <canvas> 元素可被用来通过 JavaScript&#xff…

【Figma】安装指南及基础操作

先前做UI设计一直都是用PS等绘图软件设计&#xff0c;但发现在纠结像素和排版问题上会花很多时间&#xff0c;再加上AI没来得及上手&#xff0c;就需要迅速出成图&#xff0c;此时通过论坛发现了figma&#xff0c;基本上可以满足足够的需求&#xff0c;并且可以在windows系统上…

程序员如何搞副业

#程序员如何搞副业&#xff1f;# 在快速发展的IT行业中&#xff0c;程序员作为技术骨干&#xff0c;通常拥有扎实的编程能力和丰富的项目经验。然而&#xff0c;随着职业生涯的深入&#xff0c;许多程序员开始思考如何进一步提升自我价值&#xff0c;实现更多的经济收益。副业成…

身份证实名认证接口的价格一般是多少呢?基于PHP身份核验接口

身份证实名认证接口分为身份证二要素、三要素、三要素人像核验接口&#xff0c;被广泛的应用于婚恋、交友、电商等等一系列行业领域&#xff0c;身份证实名认证需要实时数据&#xff0c;对于数据源来说也需要可靠&#xff0c;那么&#xff0c;身份证实名认证的价格是不是很贵呢…