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

LeetCode 面试题 02.08. 环路检测

文章目录

  • 一、题目
  • 二、C# 题解

一、题目

  给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。若环不存在,请返回 null

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

  点击此处跳转题目。

示例 1:

在这里插入图片描述

输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

在这里插入图片描述

输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

在这里插入图片描述

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

进阶:

  • 你是否可以不用额外空间解决此题?

二、C# 题解

  使用快慢指针 p、q 依次遍历,可以证明,当快慢指针相交时,此时慢指针 p 和头指针 head 前进相交处即为环路开头节点:

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode DetectCycle(ListNode head) {if (head == null) return null;ListNode p = head, q = p;//  快慢指针相交do {if (p != null) p = p.next;if (q != null) q = q.next;if (q != null) q = q.next;} while (p != q);if (p == null) return null; // 检查空// 寻找环路开头节点while (p != head) {p = p.next;head = head.next;}return p;}
}
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)

相关文章:

LeetCode 面试题 02.08. 环路检测

文章目录 一、题目二、C# 题解 一、题目 给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。若环不存在,请返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了…...

【Linux】线程安全-生产者消费者模型

文章目录 生产者消费者模型123规则应用场景优点忙闲不均生产者和消费者解耦支持高并发 代码模拟 生产者消费者模型 123规则 1个线程安全的队列:只要保证先进先出特性的数据结构都可以称为队列 这个队列要保证互斥(就是保证当前只有一个线程对队列进行操…...

优化(2) 2023/09/03

今天重新温习了下clean abap,以前只是偶尔打开看几眼。今天把有些自己不熟悉的地方,重点研究了下。有几个点可以在以后工作使用。这几点可能并不能提升程序效率,但会大大提高代码可读性和代码的可扩展性: 用insert XXX into tabl…...

Swap and Reverse 题解

Swap and Reverse 题面翻译 题目描述 本题共有 t t t 组数据。 给定一个长度为 n n n 的字符串 s s s 和一个整数 k k k, s s s 只包含小写字母,你可以进行若干次操作(可以是零次),具体操作如下: 选…...

单元测试:优雅编写Kotlin单元测试

一、MockK简介 MockK是一款功能强大、易于使用的Kotlin mocking框架。在编写单元测试时,MockK能够帮助我们简化代码、提高测试覆盖率,并改善测试的可维护性。除了基本用法外,MockK还提供了许多额外的功能和灵活的用法,让我们能够…...

深度学习入门教学——卷积神经网络CNN

目录 一、CNN简介 一、输入层 二、卷积层 三、池化层 四、全连接层 一、CNN简介 1、应用领域 检测任务 分类与检索 超分辨率重构 2、卷积网络与传统网咯的区别 传统神经网络和卷积神经网络都是用来提取特征的。神经网络: 可以将其看作是一个二维的。卷积神经…...

【MySQL】MySQL系统变量(system variables)列表(mysqld --verbose --help的结果例)

文章目录 【MySQL】MySQL系统变量(system variables)列表(mysqld --verbose --help的结果例)mysqld --verbose --help的结果例参考 【免责声明】文章仅供学习交流,观点代表个人,与任何公司无关。 编辑|SQL和…...

Python学习之四 数据输入与输出

(一) 脚本编程 前面的章节,组要学习了一些简单的Python编程,使用的是交互式解释器,本章节将开始进行脚本编程。可以使用多种编辑器或者IDE完成编码,主要使用vim。 参考前续小节的写法,我们给a、b分别赋值3和5。 在终端运行程序后发现,没有任何输出。这就是本次我们将要…...

VBA技术资料MF51:VBA_在Excel中突出显示唯一值

【分享成果,随喜正能量】世间万物,因果循环不休,你的善心善行,都可能成为你的善缘善果。每天忆佛念佛,每天都在佛菩萨的加持下生活,自然吉祥如意,法喜充满。 。 我给VBA的定义:VBA是…...

Mqtt学习笔记--交叉编译移植(1)

简述 Mqtt目前在物联网行业的应用比较多,mqtt属于应用层的一个中间件,这个中间件实现消息的订阅发布机制。网上介绍Mqtt的实现原来的比较多,这里不细介绍。 其实在我们之前的产品中,自己也开发的有类似的中间件,除了具…...

Gateway的服务网关

Gateway服务网关 Gateway网关是我们服务的守门神&#xff0c;所有微服务的统一入口。 网关的核心功能特性&#xff1a; 请求路由 权限控制 限流 架构如下&#xff1a; gateway使用 引入依赖 创建gateway服务&#xff0c;引入依赖 <!--网关--> <dependency>…...

信息化发展18

存储技术 1 、存储分类 2 、常用存储模式的技术与应用对比&#xff1a; ( 1 &#xff09; 存储虚拟化&#xff08; Storage Virtualization &#xff09; 是“ 云存储” 的核心技术之一。 它带给人们直接的好处是提高了存储利用率&#xff0c; 降低了存储成本&#xff0c; 简…...

TypeScript学习 + 贪吃蛇项目

TypeSCript简介 TypeScript是JavaScript的超集。它对JS进行了扩展&#xff0c;向JS中引入了类型的概念&#xff0c;并添加了许多新的特性。TS代码需要通过编译器编译为JS&#xff0c;然后再交由JS解析器执行。TS完全兼容JS&#xff0c;换言之&#xff0c;任何的JS代码都可以直…...

YOLO-NAS详细教程-介绍如何进行物体检测

对象检测是计算机视觉中的一项核心任务,可以检测和分类图像中的边界框。自从深度学习首次取得突破以来,它就以极快的速度获得普及和普及,并推动了医疗领域、监控、智能购物等众多公司的发展。考虑到它最终满足了两个基本需求,这一点也就不足为奇了端到端方式:找到所有当前…...

容器没有命令时,如何查看进程、容器executable file not found in $PATH: unknown

前言 当容器没有ps -ef命令时&#xff0c;可以通过以下的命令来查看容器的进程。 docker container top查看容器运行的进程&#xff08;该命令很有用&#xff09; #docker container top 命令用于查看容器运行的进程 #当容器里面没有ps -ef命令时&#xff0c;使用docker con…...

如何使用 Amazon EMR 在 Amazon EKS 上构建可靠、高效、用户友好的 Spark 平台

这是 SafeGraph 技术主管经理 Nan Zhu 与亚马逊云科技高级解决方案架构师 Dave Thibault 共同撰写的特约文章。 SafeGraph 是一家地理空间数据公司&#xff0c;管理着全球超过 4100 万个兴趣点&#xff08;POI&#xff0c;Point of Interest&#xff09;&#xff0c;提供品牌隶…...

国产IDE如何获得捐赠和风险投资

有人在开发VB6 脚本工具&#xff0c;有人在开发VB6的插件&#xff0c;把VB6变成VSCODE界面模式&#xff0c;再加上NUGET&#xff0c;NPM等包管理器原理的在线组件、源码下载功能。 还有TWINBASIC几乎80%代替了VB6&#xff0c;radbasic一直封闭&#xff0c;听说也收到了不少众筹…...

【数学建模】清风数模正课5 相关性分析

相关系数 相关性分析的关键是计算相关系数&#xff0c;在本节课中将会介绍两种常用的相关系数&#xff1a;皮尔逊相关系数&#xff08;Pearson&#xff09;和斯皮尔曼相关系数&#xff08;Spearman&#xff09;。 它们可以用来衡量两个变量间相关性的大小&#xff0c;对于不同…...

Java设计模式:一、六大设计原则-03:里氏替换原则

文章目录 一、定义&#xff1a;里氏替换原则1.1 里氏替换原则1.2 里氏替换原则的作用 二、模拟场景&#xff1a;里氏替换原则三、违背方案&#xff1a;里氏替换原则3.1 工程结构3.2 储蓄卡和信用卡3.2.1 储蓄卡3.2.2 信用卡 3.3 单元测试3.3.1 储蓄卡测试3.3.2 信用卡测试 四、…...

jmeter 固定定时器

固定定时器&#xff08;Constant Timer&#xff09;是一个定时器元件&#xff0c;可以在线程组中的每个线程之间添加固定的延迟时间。固定定时器会对每个线程的执行进行一定的暂停。 聊一下和线程组中的调度器对线程组执行时长的影响&#xff1a; 相同&#xff1a; 都会影响线…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...