( 链表) 142. 环形链表 II——【Leetcode每日一题】

news/2024/2/28 9:51:10

❓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 , 1 0 4 ] [0, 10^4] [0,104]
  • − 1 0 5 < = N o d e . v a l < = 1 0 5 -10^5 <= Node.val <= 10^5 105<=Node.val<=105
  • pos 的值为 -1 或者链表中的一个有效索引

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

💡思路:快慢指针

我们使用两个指针,slowfast,它们起始分别指向链表的头部head 和头部的下一个节点head.next

  • 随后,slow 指针每次向后移动一个位置,而 fast 指针向后移动两个位置。
  • 如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇。

如下图所示,设链表中环外部分的长度为 aslow 指针进入环后,又走了 b 的距离与 fast 相遇。此时,fast 指针已经走完了环的 n 圈,因此它走过的总距离为: a + n ( b + c ) + b a+n(b+c)+b a+n(b+c)+b

在这里插入图片描述
根据题意,任意时刻,fast指针走过的距离都为 slow 指针的 2 倍。因此,我们有
a + ( n + 1 ) b + n c = 2 ( a + b ) a+(n+1)b+nc=2(a+b) a+(n+1)b+nc=2(a+b)
整理得:
a = c + ( n − 1 ) ( b + c ) a=c+(n−1)(b+c) a=c+(n1)(b+c)
我们会发现:从相遇点到入环点的距离加上 n−1 圈的环长,恰好等于从链表头部到入环点的距离。

因此,当发现 slowfast 相遇后,我们让 fast 指向链表头部 headslow 指向slow 的下一个:

  • 随后, fastslow 每次向后移动一个位置
  • 最终,它们会在 入环点 相遇。

🍁代码:(Java、C++)

Java

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(head == null) return null;ListNode slow = head;ListNode fast = head.next;while(fast != null && fast.next != null){if(slow == fast) break;slow = slow.next;fast = fast.next.next;}if(fast == null || fast.next == null) return null;fast = head;slow = slow.next;while(slow != fast){slow = slow.next;fast = fast.next;}return slow;}
}

C++

/*** 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) {if(head == NULL) return NULL;ListNode* slow = head;ListNode* fast = head->next;while(fast != NULL && fast->next != NULL){if(slow == fast) break;slow = slow->next;fast = fast->next->next;}if(fast == NULL || fast->next == NULL) return NULL;fast = head;slow = slow->next;while(slow != fast){slow = slow->next;fast = fast->next;}return slow;}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为链表中节点的数目。在最初判断快慢指针是否相遇时,slow 指针走过的距离不会超过链表的总长度;随后寻找入环点时,走过的距离也不会超过链表的总长度。因此,总的执行时间为 O ( N ) + O ( N ) = O ( N ) O(N)+O(N)=O(N) O(N)+O(N)=O(N)
  • 空间复杂度 O ( 1 ) O(1) O(1),我们只使用了 slow, fast 两个指针。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/94028.html

相关文章

GaussDB内存过载分析

问题现象 数据库进程内存占比较高 长时间占比较高 观察监控平台内存占用的变化曲线&#xff0c;无论当前数据库是否有业务在运行&#xff0c;数据库进程内存占总机器内存的比例长时间处于较高状态&#xff0c;且不下降。执行作业期间占比较高 数据库进程在没有业务执行时&…

tolua源码分析(六) C#委托使用lua函数的机制实现

tolua源码分析&#xff08;六&#xff09; C#委托使用lua函数的机制实现 上一节我们讨论lua层如何使用C#的enum以及使用enum需要注意的事项。这一节我们将讨论项目日常开发中经常会用到的委托注册机制&#xff0c;即C#层暴露若干委托和事件&#xff0c;然后在lua层进行注册&…

Systrace系列11 —— Triple Buffer 解读

本文主要是对 Systrace 中的 Triple Buffer 进行简单介绍,简单介绍了如何在 Systrace 中判断卡顿情况的发生,进行初步的定位和分析,以及介绍 Triple Buffer 的引入对性能的影响。 怎么定义掉帧? Systrace 中可以看到应用的掉帧情况,我们经常看到说主线程超过 16.6 ms 就会…

【SQL Server】数据库开发指南(六)索引和视图的使用技巧、方法与综合应用

本系列博文还在更新中&#xff0c;收录在专栏&#xff1a;#MS-SQL Server 专栏中。 本系列文章列表如下&#xff1a; 【SQL Server】 Linux 运维下对 SQL Server 进行安装、升级、回滚、卸载操作 【SQL Server】数据库开发指南&#xff08;一&#xff09;数据库设计 【SQL Se…

SM3_CNC,轴组,G代码解析,CNC运动控制

硬件要求&#xff1a; 中型PLC&#xff08;汇川AM600&#xff0c;禾川HCQ0&#xff09;&#xff0c;且带 SM3_CNC.library 库&#xff08;3.5.6支持离线仿真&#xff09; G代码标准&#xff1a; DIN66025 DIN66025-1标准G0 运动定位 G1 线性插补 G2 顺圆插补 G3 …

工程师是怎样对待开源

工程师如何对待开源 本文是笔者作为一个在知名科技企业内从事开源相关工作超过 20 年的工程师&#xff0c;亲身经历或者亲眼目睹很多工程师对待开源软件的优秀实践&#xff0c;也看到了很多 Bad Cases&#xff0c;所以想把自己的一些心得体会写在这里&#xff0c;供工程师进行…

MyCat|Shardingsphere-proxy:jdbc连接MySQL8.0.33的query_cache_size异常解决方案

当前版本&#xff1a;MySQL 8.0.33 &#xff0c;Mycat-server-1.6.7.6-release-20220524173810-win&#xff0c;apache-shardingsphere-5.3.2-shardingsphere-proxy-bin&#xff0c;jdk 1.8 1. 问题的主要背景 MySQL 8.0.33版本&#xff0c;搭建了主从复制&#xff0c;需要借…

Linux的进程信号(上)

文章目录 1. 信号入门2. 技术应用角度的信号3. 信号概念4. 信号处理常见方式5. 产生信号5.1 通过终端按键产生信号5.2 调用系统函数向进程发信号5.3 由软件条件产生信号5.4 硬件异常产生信号 6. Core Dump 1. 信号入门 在生活中&#xff0c;比如红绿灯&#xff0c;铃声这些&am…

每日一题——两数之和(返回下标和返回数值两种情况)

每日一题 两数之和 题目链接 思路 注&#xff1a;本题只采用暴力解法&#xff0c;时间复杂度为O(n2)&#xff0c;如果采用哈希表&#xff0c;可以将时间复杂度降到O(n)&#xff0c;但由于笔者还未对哈希表展开学习&#xff0c;故不做讨论 我们直接用两层for循环来解决问题 第…

【Python】内置函数

文章目录 反射相关【4】基础数据类型相关【38】和数字相关&#xff08;14&#xff09;数据类型 <4>bool([x])int((x, base10)float([x])complex([real[, imag]]) 进制转换 <3>bin(x)oct(x)hex(x) 数学运算&#xff08;7&#xff09;abs(x)divmod(a, b)round(x [, n…

Scikit-LLM:将大语言模型整合进Sklearn的工作流

我们以前介绍过Pandas和ChaGPT整合&#xff0c;这样可以不了解Pandas的情况下对DataFrame进行操作。现在又有人开源了Scikit-LLM&#xff0c;它结合了强大的语言模型&#xff0c;如ChatGPT和scikit-learn。但这个并不是让我们自动化scikit-learn&#xff0c;而是将scikit-learn…

第三十九章 青格郎当(青衣弹灵诞生)

“巴哥奔&#xff0c;我们诚挚邀请你加入金马弹灵&#xff0c;着青衣&#xff0c;事渲染&#xff0c;你愿意么&#xff1f;” 蓝衣弹灵话音刚落&#xff0c;大家一齐睁开眼睛&#xff0c;直愣愣的盯着巴哥奔。 “唔~~~可~” 好半天&#xff0c;巴哥奔才憋出这个字&#xff0c;刚…

uCOSii任务管理

uCOSii任务管理 主要用来测试uCOSii“创建任务,挂起任务,恢复任务,发送删除任务请求,删除任务”。 在os_cfg.h中 #define OS_LOWEST_PRIO 63u //设置最低优先级为63,则空闲任务优先级OS_TASK_IDLE_PRIO就等于63 //OS_PRIO_SELF为255,因此OS_LOWEST_PRIO<255 注意&a…

定积分的计算(牛顿-莱布尼茨公式)习题

前置知识&#xff1a;定积分的计算&#xff08;牛顿-莱布尼茨公式&#xff09; 习题1 计算 ∫ 0 2 ( x 2 − 2 x 3 ) d x \int_0^2(x^2-2x3)dx ∫02​(x2−2x3)dx 解&#xff1a; \qquad 原式 ( 1 3 x 3 − x 2 3 x ) ∣ 0 2 ( 8 3 − 4 6 ) − 0 14 3 (\dfrac 13x^3-…

Emacs之定制化mode line(第一百零二)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只有行动才是治疗恐惧和懒惰的唯一良药. 更多原创,欢迎关注:Android…

java基础入门-15-【集合(Map可变参数集合工具类)】

Java基础入门-15-【集合(Map&可变参数&集合工具类)】 24、集合(Map&可变参数&集合工具类)双列集合的特点1.Map集合1.1 Map集合概述和特点【理解】1.2 Map集合的基本功能【应用】1.3 Map集合的获取功能【应用】1.4 Map集合的遍历(方式1)【应用】----- 键找值…

【MySQL约束】数据管理实用指南

1、数据库约束的认识 数据库约束的概念&#xff1a;数据库的约束是关系型数据库的一个重要的功能&#xff0c;它提供了一种“校验数据”合法性的机制&#xff0c;能够保证数据的“完整性”、“准确性”和“正确性” 数据库的约束&#xff1a; not null&#xff1a;不能存储 nul…

带你深入了解Fragment懒加载

Fragment懒加载是一种优化技术&#xff0c;用于在Android应用中延迟加载和初始化Fragment的内容&#xff0c;以提高应用性能和用户体验。它的核心思想是只有在Fragment可见时才加载数据和执行相关操作&#xff0c;而不是在Fragment创建或添加到Activity时立即加载。 懒加载的主…

java boot项目认识一下三种格式的配置文件

之前我们在 application.properties 中写了很多配置 但boot并不是只有这种配置方式 boot提供了三种配置方式给我们 话不多说 直接上代码 我们先将 resources下的 application.properties给他干掉 然后在下面创建一个 application.yml 在下面编写代码如下 server:port: 81这…

方法——检查参数的有效性

检查参数的有效性 绝大多数方法和构造方法对于传递给它们的参数都会有某些限制,比如对象引用不能为null,比如必须是正数等.你应该在文档中(或者注释中)清楚地指出所有这些限制,并且在方法体的开头检查参数,并且强制施加这些限制.如果做不到这一点,检测出错误的可能性就很小,即…
最新文章