开发者社区> 流楚丶格念> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

142. 环形链表 II

简介: 142. 环形链表 II
+关注继续查看

142. 环形链表 II


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


为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。


说明:不允许修改给定的链表。


进阶:


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


示例 1:


image


输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点


解释:链表中有一个环,其尾部连接到第二个节点。


示例 2:


image


输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点


解释:链表中有一个环,其尾部连接到第一个节点。


示例 3:


image


输入:head = [1], pos = -1
输出:返回 null


解释:链表中没有环。


题解


对于链表找环路的问题,有一个通用的解法——快慢指针(Floyd 判圈法)。


给定两个指针,分别命名为 slow 和 fast,起始位置在链表的开头。每次 fast 前进两步,slow 前进一步。如果 fast可以走到尽头,那么说明没有环路;如果 fast 可以无限走下去,那么说明一定有环路,且一定存在一个时刻 slow 和 fast 相遇。当 slow 和 fast 第一次相遇时,我们将 fast 重新移动到链表开头,并让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时,相遇的节点即为环路的开始点。


双指针法图解 ※


双指针法图解


代码


/**
 * 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) {
        ListNode *slow=head,*fast=head;
        // 判断是否存在环路
        do{
            // 如果不成环 返回nullptr
            if (!fast || !fast->next) 
                return nullptr;
            fast = fast->next->next;
            slow = slow->next;    
        }while(fast != slow);
        // 如果存在,查找环路节点
        fast = head;
        while (fast != slow){
        slow = slow->next;
        fast = fast->next;
        }
        return fast;
    }
};

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
< 数据结构 > 单向环形链表
目录 1、例题引入 2、何为带环链表 3、题解思路 4、拓展问题 (1)slow一次走1步,fast一次走2步,一定能追上吗? (2)slow一次走1步,fast一次走3步,能追上吗?fast一次走4步呢?n步呢? (3)链表环的入口点在哪呢?
18 0
网约车业务系统 网络安全防护评测体系
网约车业务系统网络安全防护评测体系:网约车安全防护测评介绍,评估依据,安全评估流程,交付成果。
131 0
云上架构和传统IT架构有什么区别及优势?
在云计算走向成熟之前,我们更应该关注系统云计算架构的细节,从传统的架构到云上大数据,实现了很多的转变。
1368 0
物联网12大安全挑战
物联网12大安全挑战
1260 0
云安全促使防火墙演变“云”火墙
本文讲的是云安全促使防火墙演变“云”火墙,在信息产业中,安全是一个令人尴尬的行当。计算、网络、存储等厂商可以骄傲地历数近年来技术性能的突飞猛进,而安全产业在不断地发展和投入之后,面对的却是越来越多、越来越麻烦的安全问题。
1325 0
云安全——被动安全防护的止痛药
本文讲的是云安全——被动安全防护的止痛药,“云安全”的设想在提出之初一直备受关注,不少人认为这是概念炒作,成不了什么气候,未必能引领下一代的安全技术,但今天我们看到“云安全”已经得到实践应用,并获得了较多数的好评。
1297 0
[20140805]批量生成awr报表.txt
[20140805]批量生成awr报表.txt --工作需要生成1天awr的报表,我记得以前在itpub上有人问过类似的问题,我当时也google,找到链接 --再翻了一下帖子,找到如下: http://www.
766 0
+关注
流楚丶格念
csdn平台优质创作者,51cto TOP博主,360图书馆科技博主,燕山大学目前大三在读,日拱一卒,功不唐捐,加油!!!
1010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载