当前位置:   article > 正文

算法小白日记-环形链表找入口_算法题找到环形列表环的入口

算法题找到环形列表环的入口

本文介绍

环形链表找入口很多题解不是很全面,本文全面解析此题

题目引入

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

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

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

进阶:

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

解法

快慢指针

快慢节点同时走

快节点必然追上慢节点

假设进入环之前,有a个节点,快慢必然在环上的某一节点相遇,慢节点走了b个节点,未走的是c个节点。

且快节点走的距离是慢节点的2倍,设a走了n圈,那么有a+n(b+c)+b = 2(a+b),

即a+(n+1)b+nc=2(a+b)得出 a = (n-1)(b+c)+c

b与c是相遇点与环的距离,那么上面的表达式就是环入口到头节点的距离为n-1圈的环的长度加c

那么当快慢指针相遇的时候,我们新起一个指针从头结点走,慢指针从相遇点走,当慢指针与新指针相遇的时候就是入口节点

!!!!!!
why

这里给小伙伴们讲一下,慢指针走c到入口节点就是式子中的+c,而(n-1)倍的环长就是一直在循环,等新节点走到入口时候,慢指针一定相对入口走完一圈。

image.png

引用文献

lettcode官方题解

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/784950
推荐阅读
相关标签
  

闽ICP备14008679号