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

news/2024/11/13 2:24:06/

❓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…