1.6 如何检测一个较大的单链表是否有环

难度系数：★★★★☆

被考查系数：★★★★★

题目描述：

单链表有环指的是单链表中某个结点的next域指向的是链表中在它之前的某一个结点，这样在链表的尾部形成一个环形结构。如何判断单链表是否有环存在？

分析与解答：

方法一：蛮力法

定义一个Set用来存放结点的引用，并将其初始化为空，从链表的头结点开始向后遍历，每遍历到一个结点就判断Set中是否引用这个结点，如果没有，说明这个结点是第一次访问，还没有形成环，那么将这个引用结点添加到指针Set中去。如果在Set中找到了同样的结点，那么说明这个结点已经被访问过了，于是就形成了环。这种方法的时间复杂度为O(n)，空间复杂度也为O(n)。

方法二：快慢指针遍历法

定义两个指针fast（快）与slow（慢），二者的初始值都指向链表头，指针slow每次前进一步，指针fast每次前进两步，两个指针同时向前移动，快指针每移动一次都要跟慢指针比较，如果快指针等于慢指针，就证明这个链表是带环的单向链表，否则，证明这个链表是不带环的循环链表。实现代码见引申部分。

引申：如果链表存在环，那么如何找出环的入口点？

分析与解答：

当链表有环的时候，如果知道环的入口点，那么在需要遍历链表或释放链表所占的空间的时候方法将会非常简单，下面主要介绍查找链表环入口点的思路。

如果单链表有环，那么按照上述方法二的思路，当走得快的指针fast与走得慢的指针slow相遇时，slow指针肯定没有遍历完链表，而fast指针已经在环内循环了n圈（1<=n）。如果slow指针走了s步，则fast指针走了2s步（fast步数还等于s加上在环上多转的n圈），假设环长为r，则满足如下关系表达式：

2s=s+nr

由此可以得到：s=nr

设整个链表长为L，入口环与相遇点距离为x，起点到环入口点的距离为a。则满足如下关系表达式：

a+x=nr

a+x=(n-1)r+r=(n-1)r+L-a

a=(n-1)r+(L-a-x)

(L-a-x)为相遇点到环入口点的距离，从链表头到环入口点的距离=(n-1)×环长+相遇点到环入口点的长度，于是从链表头与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

实现代码如下：

程序的运行结果为

运行结果分析：

示例代码中给出的链表为：1->2->3->4->5->6->7->3（3实际代表链表第三个结点）。因此，IsLoop函数返回的结果为两个指针相遇的结点，所以，链表有环，通过函数FindLoopNode可以获取到环的入口点为3。

算法性能分析：

这种方法只需要对链表进行一次遍历，因此，时间复杂度为O(n)。另外由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O(1)。