142. 环形链表 II

题目描述

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

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

不允许修改 链表。

示例 1:

img

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

示例 2:

img

输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

img

输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。

提示:

  • 链表中节点的数目范围在范围 [0, 104]
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

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

解答

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {// 双指针法// 快慢指针分别为 fast 和slow,fast每次走两步,slow每次走一步// 快指针走的路程为f,慢指针走的路程为s// 环上节点数为b// 相遇必然是在环内,相遇时,f = 2s, f = s + nb, n为套的圈数// 故可得第一次相遇时 s = nb, 此时让快指针回到链表起点与慢指针同速度走// 若环之前长度为a,则 a + nb必然时在环的入口(所以必然快慢指针会在环口相遇)ListNode *fast = head, *slow = head;while(true){if(fast == nullptr || fast->next == nullptr){return nullptr;}fast = fast->next->next;slow = slow->next;// 第一次相遇在环内if(slow == fast) break;}// 快指针会头节点和慢指针同速度走fast = head;while(fast != slow){slow = slow->next;fast = fast->next;}return fast;}// 集合法(哈希表法)ListNode *detectCycle1(ListNode *head) {unordered_set<ListNode *> s;// 指针没到尾节点 且 当前节点没重复出现while(head && s.find(head) == s.end()){s.insert(head);head = head->next;}if(head){return head;}return NULL;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

运维监控学习笔记8

在服务器端&#xff0c;我们添加了nginx-server的主机&#xff1a; 在解决Error问题的过程中&#xff0c;我还通过zabbix_get这个命令进行了测试&#xff0c;发现是没有的&#xff0c;后来确认是在web页面配置的过程中&#xff0c;我输错了密码。 yum install zabbix-getzabbi…

应急响应-Webshell

文章目录 一、Webshell概述什么是WebshellWebshell分类基于编程语言基于文件大小/提供的功能多少 Webshell 检测方法 二、常规处置方法三、技术指南1、初步预判2、 Webshell排查3、Web日志分析&#xff08;查找攻击路径及失陷原因&#xff09;4、系统排查4.1 Windows4.2 Linux …

淘宝API接口的实时数据和缓存数据区别

电商API接口实时数据是指通过API接口获取到的与电商相关的实时数据。这些数据可以包括商品库存、订单状态、销售额、用户活跃度等信息。 通过电商API接口&#xff0c;可以实时获取到电商平台上的各种数据&#xff0c;这些数据可以帮助企业或开发者做出及时的决策和分析。例如&…

SAP MM学习笔记23-购买发注的账户分配类型(勘定Category)

SAP中控制财务凭证过账科目的是 账号分配类型&#xff08;勘定Category&#xff09;栏目。 ・账号分配类型&#xff08;勘定Category&#xff09;有&#xff1a; 1&#xff0c;K 原价Center&#xff08;成本中心。用于消耗物料采购 的过账&#xff09; 2&#xff0c;E 得意先…

医疗PACS源码,支持三维多平面重建、三维容积重建、三维表面重建、三维虚拟内窥镜

C/S架构的PACS系统源码&#xff0c;PACS主要进行病人信息和影像的获取、处理、存储、调阅、检索、管理&#xff0c;并通过网络向全院提供病人检查影像及诊断报告&#xff1b;各影像科室之间共享不同设备的病人检查影像及诊断报告;在诊断工作站上&#xff0c;调阅HIS中病人的其它…

服务器数据恢复-HP EVA存储常见故障的数据恢复流程

EVA存储原理&#xff1a; EVA系列存储是以虚拟化存储为实现目的的中高端存储设备&#xff0c;内部的结构组成完全不同于其他的存储设备&#xff0c;RAID在EVA内部称之为VRAID。 EVA会在每个物理磁盘&#xff08;PV&#xff09;的0扇区写入签名&#xff0c;签名后PV会被分配到不…

2023企业微信0day漏洞复现以及处理意见

2023企业微信0day漏洞复现以及处理意见 一、 漏洞概述二、 影响版本三、 漏洞复现小龙POC检测脚本: 四、 整改意见 免责声明&#xff1a;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#x…

DevOps系列文章 之 Gitlab+Docker自动部署SpringBoot

1.环境要求 以下服务器的操作系统均为Centos7 服务器A&#xff1a;Gitlab服务器B&#xff1a;GitlabRunner、Docker、docker-compose、Java1.8、maven3.6.3、git ps&#xff1a;这里可以把服务器B的GitlabRunner、Java1.8、maven3.6.3、git单独提出来&#xff0c;独立部署&a…

【MySQL】为什么不推荐使用uuid或者雪花id作为主键?

文章目录 1.原因2.使用uuid(或雪花ID&#xff09;和自增id的索引结构对比2.1 使用自增id的内部结构2.2 使用uuid(或雪花ID&#xff09;的索引内部结构2.3 使用自增id的缺点 1.原因 使用UUID或雪花ID&#xff08;Snowflake ID&#xff09;作为主键并不是完全不推荐的&#xff0…

二叉树的存储结构(链式存储)—— 数据结构与算法

&#x1f636;‍&#x1f32b;️Take your time ! &#x1f636;‍&#x1f32b;️ &#x1f4a5;个人主页&#xff1a;&#x1f525;&#x1f525;&#x1f525;大魔王&#x1f525;&#x1f525;&#x1f525; &#x1f4a5;代码仓库&#xff1a;&#x1f525;&#x1f525;魔…

Linux 操作文件的系统调用

一、系统调用 系统调用表现出来的形式和库函数看着是一样的&#xff0c;但是系统调用的实现是在内核中&#xff0c;一旦执行系统调用以后&#xff0c;会产生中断&#xff0c;陷入内核&#xff0c;内核去执行相应的代码。我们无法直接去执行内核的代码&#xff0c;系统调用执行…

零基础看懂免费开源的Stable Diffusion

文章目录 前言Diffusion模型推理过程训练过程 Stable Diffusion模型参考 前言 前面一篇文章主要讲了扩散模型的理论基础&#xff0c;还没看过上篇的小伙伴可以点击查看&#xff1a;DDPM理论基础。这篇我们主要讲一下一经推出&#xff0c;就火爆全网的Stable Diffusion模型。St…

SQL-每日一题【1341. 电影评分】

题目 表&#xff1a;Movies 表&#xff1a;Users 请你编写一个解决方案&#xff1a; 查找评论电影数量最多的用户名。如果出现平局&#xff0c;返回字典序较小的用户名。查找在 February 2020 平均评分最高 的电影名称。如果出现平局&#xff0c;返回字典序较小的电影名称。 …

「鲸脸识别」已上线,夏威夷大学用 5 万张图像训练识别模型,平均精度 0.869

内容一览&#xff1a;人脸识别可以锁定人类身份&#xff0c;这一技术延申到鲸类&#xff0c;便有了「背鳍识别」。「背鳍识别」是利用图像识别技术&#xff0c;通过背鳍识别鲸类物种。传统的图像识别依赖于卷积神经网络 (CNN) 模型&#xff0c;需要大量训练图像&#xff0c;并且…

《3D 数学基础》12 几何图元

目录 1 表达图元的方法 1.1 隐式表示法 1.2 参数表示 1.3 直接表示 2. 直线和射线 2.1 射线的不同表示法 2.1.1 两点表示 2.1.2 参数表示 2.1.3 相互转换 2.2 直线的不同表示法 2.2.1 隐式表示法 2.2.2 斜截式 2.2.3 相互转换 3. 球 3.1 隐式表示 1 表达图元的方…

【C语言】每日一题(多数元素)

多数元素&#xff0c;链接奉上 方法 1.摩尔投票2.合理但错误的方法2.1暴力循环2.2排序求出中间元素中间元素 1.摩尔投票 先来简单的介绍摩尔投票&#xff1a; 摩尔投票是一种用来解决绝对众数问题的算法。 什么是绝对众数呢&#xff1f; 在一个集合中&#xff0c;如果一个元素…

PHP最简单自定义自己的框架model使用(七)

1、实现model使用效果 2、自动加载model,KJ.php //自动加载文件public static function _autoload($className){switch ($className){//自动model类case substr($className,-5)Model:$path MODEL./.$className..php;if(is_file($path)) include $path;break;//自动加载控制器…

机器学习理论笔记(一):初识机器学习

文章目录 1 前言&#xff1a;蓝色是天的机器学习笔记专栏1.1 专栏初衷与定位1.2 本文主要内容 2 机器学习的定义2.1 机器学习的本质2.2 机器学习的分类 3 机器学习的基本术语4 探索"没有免费的午餐"定理&#xff08;NFL&#xff09;5 结语 1 前言&#xff1a;蓝色是天…

隧道人员定位方案

针对隧道环境的人员定位方案&#xff0c;UWB定位技术同样可以提供高精度和可靠的定位服务。以下是一个可行的方案&#xff1a; 部署基站网络&#xff1a;在隧道内建立一个基站网络&#xff0c;基站需要均匀分布在各个关键位置&#xff0c;以确保全方位的覆盖。由于隧道的特殊环…

一、Dubbo 简介与架构

一、Dubbo 简介与架构 1.1 应用架构演进过程 单体应用&#xff1a;JEE、MVC分布式应用&#xff1a;SOA、微服务化 1.2 Dubbo 简介一种分布式 RPC 框架&#xff0c;对专业知识&#xff08;序列化/反序列化、网络、多线程、设计模式、性能优化等&#xff09;进行了更高层的抽象和…