LeetCode 142.环形链表II

在这里插入图片描述

文章目录

  • 💡题目分析
  • 💡解题思路
  • 💡深度思考
  • 🔔接口源码

在这里插入图片描述
题目链接👉 LeetCode 142.环形链表II👈

💡题目分析

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

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

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

💡解题思路

先使用快慢指针找到相遇点(定义两个指针,一个快指针、一个慢指针,让快指针一次走一步,慢指针一次走两步,如果存在环的话,快指针会先进环,一直在环中循环的走,等到慢指针也进入环中循环,快指针追击慢指针,最后它们一定会相遇,找到相遇点),然后一个指针从相遇点开始走,一个指针从链表头开始走,最终他们会在入口点相遇

💡深度思考

在这里插入图片描述
fast走的路程是slow的2倍

假设:
链表头 ---- 环入口点的距离:L
环入口点 ---- 相遇点的距离:X
环的长度:C
slow走的路程是多少?

slow走的路程为:L+X

分析:有没有可能slow进环转了几圈才追上?

不可能!1圈之内,fast必然追上slow,因为他们之间距离每次缩小1,不会错过,slow走1圈,fast都已经走2圈了,肯定追上了。

fast走的路程是多少?

fast走的路程为:L+C+X ?
在这里插入图片描述

fast走的路程应该为:L + n*C + X
假设n是slow进环前,fast在环里面转的圈数
在这里插入图片描述
在这里插入图片描述

🔔接口源码

struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* slow = head,*fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;//带环if(slow == fast){//求入口点struct ListNode* meet = slow;while(head != meet){head = head->next;meet = meet->next;}return meet;}}return NULL;
}

在这里插入图片描述

🥰希望烙铁们能够理解欧!

总结🥰
以上就是本题讲解的全部内容啦🥳🥳🥳🥳
本文章所在【C/C++刷题系列】专栏,感兴趣的烙铁可以订阅本专栏哦🥳🥳🥳
前途很远,也很暗,但是不要怕,不怕的人面前才有路。💕💕💕
小的会继续学习,继续努力带来更好的作品😊😊😊
创作写文不易,还多请各位大佬uu们多多支持哦🥰🥰🥰

请添加图片描述

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

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

相关文章

优化GitHub网站访问慢的问题

方法一、修改host文件解决 大型网站服务器都不会是只有一台服务器,而是多台服务器组成的集群一起对外提供服务。 使用站长工具测速,找一个速度比较快的服务器。 图中可以看到140.82.121.4这个ip比较快, 下面修改hosts: Mac 在 /etc/hosts 中&#x…

蓝牙资讯|中国智能家居前景广阔,蓝牙Mesh照明持续火爆

据俄罗斯卫星通讯社报道,中国已成为全球最大的智能家居消费国,占全球50%—60%的市场份额。未来,随着人工智能技术的发展以及智能家居生态的不断进步,智能家居在中国的渗透率将加速提升。德国斯塔蒂斯塔调查公司数据显示&#xff0…

Redis在Java中的基本使用

本片将介绍 Redis 在 Java 中的基本使用 文章目录 1、使用jedis操作redis1.1、Jedis简介1.2、引入jedis的Maven依赖1.2、获取连接1.3、使用实例 2、对于JedisPooled的使用2.1、使用JedisPooled2.2、关于连接池 3、SpringBoot下使用Redis3.1、引入Maven依赖3.2、配置Redis连接3.…

excel逻辑函数篇2

1、IF(logical_test,[value_if_true],[value_if_false]):判断是否满足某个条件,如果满足返回一个值,如果不满足则返回另一个值 if(条件,条件成立返回的值,条件不成立返回的值) 2、IFS(logical_test1,value_if_true1,…):检查是否…

网络安全--wazuh环境配置及漏洞复现

目录 一、wazuh配置 二、wazuh案例复现 一、wazuh配置 1.1进入官网下载OVA启动软件 Virtual Machine (OVA) - Installation alternatives (wazuh.com) 1.2点击启动部署,傻瓜式操作 1.3通过账号:wazuh-user,密码:wazuh进入wazuh…

删除链表中的节点(力扣)

目录 题目: 看着花里胡哨,小卡拉米四行代码秒杀! 示例: 思路: 代码: 题目: 看着花里胡哨,小卡拉米四行代码秒杀! 示例: 思路: 把后一个节点的…

动手学深度学习—卷积神经网络LeNet(代码详解)

1. LeNet LeNet由两个部分组成: 卷积编码器:由两个卷积层组成;全连接层密集块:由三个全连接层组成。 每个卷积块中的基本单元是一个卷积层、一个sigmoid激活函数和平均汇聚层;每个卷积层使用55卷积核和一个sigmoid激…

【Redis从头学-5】Redis中的List数据类型实战场景之天猫热销榜单

🧑‍💻作者名称:DaenCode 🎤作者简介:啥技术都喜欢捣鼓捣鼓,喜欢分享技术、经验、生活。 😎人生感悟:尝尽人生百味,方知世间冷暖。 📖所属专栏:Re…

linux RabbitMQ-3.8.5 安装

软件版本操作系统CentOS Linux release 7.9.2009erlangerlang-23.0.2-1.el7.x86_64rabbitMQrabbitmq-server-3.8.5-1.el7 RabbitMQ的安装首先需要安装Erlang,因为它是基于Erlang的VM运行的。 RabbitMQ安装需要依赖:socat和logrotate,logrotate操作系统已经存在了&…

图论相关问题

1. 拓扑排序bitset 第一次使用bitset&#xff0c;复杂度&#xff1a;N/32&#xff0c;比N小 所以总的时间复杂度为O(N*(NM)/32) #include <iostream> #include <bitset> #include <queue> using namespace std; const int N 3e420; bitset<N> f[N];…

使用低版本vcpkg时,bootstrap-vcpkg.bat无法生成vcpkg.exe的可能原因

缘由 需要使用vcpkg中低版本的第三方库&#xff0c;下载vcpkg后&#xff0c;回退至指定版本&#xff0c;运行bootstrap-vcpkg.bat生成vcpkg.exe时&#xff0c;命令行窗口总是一闪而过&#xff0c;但是vcpkg.exe却没有生成。 添加pause&#xff0c;查看错误 编辑bootstrap-vc…

09_Redlock算法和底层源码分析

Redlock算法和底层源码分析 一、当前代码为8.0版接上一步 自研分布式锁的重点&#xff1a; 按照juc里面Lock接口规范进行编写lock加锁关键逻辑 加锁&#xff1a;在redis中&#xff0c;加锁实际上是给key设置一个值&#xff0c;为避免死锁&#xff0c;并给key一个过期时间自旋…

腾讯云轻量应用服务器配置(详细版)

腾讯云轻量应用服务器CPU内存带宽配置高&#xff0c;成本很低&#xff0c;腾讯云百科来详细说下腾讯云服务器从购买、配置到网站上线全流程&#xff0c;包括轻量服务器配置选择、应用镜像选择、重置密码、防火墙开放端口教程等详细教程&#xff1a; 目录 一&#xff1a;注册腾…

vue的开发者工具下载『保姆级别』

1.先进官网 极简插件_Chrome扩展插件商店_优质crx应用下载 (zzzmh.cn) 2.搜索vue devtools&#xff0c;点击进去 3.下载插件 4.下载到文件下你自己的文件下&#xff1a;我的是下载到E盘下。 5.压缩到当前目录下 6.电脑进入拓展程序&#xff08;不同的浏览器操作不同&#xff…

在Visual Studio上,使用OpenCV实现人脸识别

1. 环境与说明 本文介绍了如何在Visual Studio上&#xff0c;使用OpenCV来实现人脸识别的功能 环境说明 : 操作系统 : windows 10 64位Visual Studio版本 : Visual Studio Community 2022 (社区版)OpenCV版本 : OpenCV-4.8.0 (2023年7月最新版) 实现效果如图所示&#xff0…

系统卡死问题分析

CPU模式 CPU Frequency Scaling (CPUFREQ) Introduction CPU频率调节设备驱动程序的功能。该驱动程序允许在运行过程中更改CPU的时钟频率。一旦CPU频率被更改,必要的电源供应电压也会根据设备树脚本(DTS)中定义的电压值进行变化。通过降低时钟速度,这种方法可以减少功耗…

CloudCompare——统计滤波

目录 1.统计滤波2.软件实现3.完整操作4.算法源码5.相关代码 本文由CSDN点云侠原创&#xff0c;CloudCompare——统计滤波&#xff0c;爬虫自重。如果你不是在点云侠的博客中看到该文章&#xff0c;那么此处便是不要脸的爬虫。 1.统计滤波 算法原理见&#xff1a;PCL 统计滤波器…

使用 Elasticsearch 轻松进行中文文本分类

本文记录下使用 Elasticsearch 进行文本分类&#xff0c;当我第一次偶然发现 Elasticsearch 时&#xff0c;就被它的易用性、速度和配置选项所吸引。每次使用 Elasticsearch&#xff0c;我都能找到一种更为简单的方法来解决我一贯通过传统的自然语言处理 (NLP) 工具和技术来解决…

韩顺平Linux 四十四--

四十四、rwx权限 权限的基本介绍 输入指令 ls -l 显示的内容如下 -rwxrw-r-- 1 root 1213 Feb 2 09:39 abc0-9位说明 第0位确定文件类型&#xff08;d , - , l , c , b) l 是链接&#xff0c;相当于 windows 的快捷方式- 代表是文件是普通文件d 是目录&#xff0c;相…

录制游戏视频的软件有哪些?分享3款软件!

“有录制游戏视频的软件推荐吗&#xff1f;最近迷上了网游&#xff0c;想录制点自己高端操作的游戏画面&#xff0c;但是不知道用什么软件录屏比较好&#xff0c;就想问问大家&#xff0c;有没有好用的录制游戏视频软件。” 在游戏领域&#xff0c;玩家们喜欢通过录制游戏视频…