牛客网高频算法题系列-BM7-链表中环的入口结点

题目描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

原题目见：BM7 链表中环的入口结点

解法一：双指针法

使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。

如果相遇了，从相遇处到入口结点的距离与头结点与入口结点的距离相同。所以将fast重新设置为头结点，fast和sow结点都一步步走，直到相遇，即为入口结点。

原理可参考：双指针算法原理详解

解法二：哈希法

使用HashSet记录链表中的结点，然后遍历链表结点：

• 如果链表中的结点在哈希表中出现过，说明链表有环，并且该结点即为入口结点，返回之

• 如果链表中的结点没有在哈希表中出现过，则将当前结点添加到哈希表中，然后判断下一个结点

最后，如果没有重复节点，则说明无环，返回null。

说明：和 牛客网高频算法题系列-BM6-判断链表中是否有环 的解法基本一致。

代码

1.01^{365} ≈ 37.7834343329   

0.99^{365} ≈ 0.02551796445   

相信坚持的力量！