判断链表环的入口

作者：空白诗007 | 2024-08-08 01:54:10

踩

判断链表环的入口

方法一：

使用hash表，遍历链表每一个节点，放入哈希表中，当待放入的节点存在于哈希表中时，这个节点就是环的入口，否则就没有环。

方法二：

假设链表link，

用两个指针，一个fast指针，每次走两步，一个slow指针，每次走一步。

当fast指针与slow指针相遇时，假设fast指针走了2s，那么slow指针走了s。

假设链表的长度为L，链表起始点与环的入口距离为a，环的长度为r，环的入口与相遇点的距离为x，

L - a = r，相遇点到环入口的距离为Y = L-a-x

相遇时fast在环上跑了n圈、slow在环上跑了m圈，其中n-m>=1，那么有等式：

2s = s + nr可知：s = nr

s = a+x+mr。

所以：a+x+mr = nr 可得：

==》a+x = (n-m)r

==》a+x = (n-m-1)r +

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】