如何判断一个单链表是否有环以及环入口

太过爱你忘了你带给我的痛 2022-05-17 02:24 488阅读 0赞

这是一个在我们学习数据结构的时候经常会遇到的问题，今天给大家带来这个问题的几种解法。

### 方法一 ###

最容易想到的办法就是遍历单链表，如果单链表有环的话那么会进入死循环，但是我们不知道单链表的长度，所以如果单链表长度很长，我们一直向下遍历，也无法分辨出是单链表还没遍历完还是进入了死循环。

所以这种解法不靠谱。

### 方法二 ###

我们可以在遍历单链表中的每个元素的时候，每遍历一个新的节点，就从头再开始遍历一次已经遍历过的节点，用新节点和之前遍历过的节点相比较，如果新节点之前遍历过的节点相同，就说明单链表有环。

![单链表][E5_8D_95_E9_93_BE_E8_A1_A81.png]

比如说已存在的单链表：A->B->C->D->E->F->G->D，在遍历到第七个节点（D）的时候，再在从头节点开始遍历到第三个节点，因为第三个集结点（D）和第七个节点相同，所以单链表一定有环。

假设从单链表头节点到环入口节点的距离是D，单链表的环长是S。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)\*(D+S)/2，可以理解成O(N\*N)。

算法没有创建额外存储空间，空间复杂度可以简单地理解成为O(1)。

所以这个算法的时间复杂度是O(N\*N)，空间复杂度是O(1)。

找环入口的话就很简单了，遍历到第一个判定单链表有环的节点（D）就是环的入口。

### 方法三 ###

考虑到方法二每遍历一个新节点的时候都需要从头开始遍历遍历一遍节点，会导致时间复杂度很高，所以我们可以把已经遍历过的节点用一个HashSet存起来，然后每遍历一个新节点的时候再去和HashSet中的元素做匹配，如果HashSet中已存在该节点，那么单链表有环。

假设从单链表头节点到环入口节点的距离是D，单链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1),所以总体的时间复杂度是1\*(D+S)=D+S，可以简单理解为O(N)。

而算法的空间复杂度还是D+S-1，可以简单地理解成O(N)。

这个算法的时间复杂度是O(N)，空间复杂度是o(N).

找环入口和方法二一样，遍历到第一个判定单链表有环的节点（D）就是环的入口。

### 方法四 ###

还有一种思路是创建两个变量slow和fast同时指向头节点，然后slow每次向后遍历一个节点，fast每次向后遍历两个节点，如果单链表没有环的话那么slow将永远追不上fast，而如果单链表有环的话slow就会追上fast。

![单链表2][2]

下面我们来模拟随着单链表的遍历slow和fast两个变量值的变化：

![单链表3][3]

可以看到遍历到第八次的时候，slow追上了fast，所以单链表有环。

假设从单链表头节点到环入口节点的距离是D，单链表的环长是S。那么循环会进行S\*K次，K为正整数，可以简单理解为O(N)。除了两个指针以外，没有使用任何额外存储空间，所以空间复杂度是O(1)。

这个算法的时间复杂地是O(N)，空间复杂度O(1)。

那么如何找到环的入口呢？下面我们来进行一个小小的数学计算:设从单链表头节点到环入口节点的距离是D,环入口到相交点的距离是X,设slow和fast第一次相遇时fast走了n圈环，slow走的距离为len，那么fast走的距离是2\*len，可以得出下面的两个等式：

len = D + X
    2 * len = D + X + n * R

两个等式相减可以的到：len = n \* R - X

通过这个等式我们可以再定义两个变量out和in，out指向单链表头节点，in指向之前slow和fast第一次相交的节点，out和in同时向后遍历，第一次相交的点就是环的入口。

![单链表4][4]

下面我们来模拟随着单链表的遍历out和in两个变量值的变化：

可以看到遍历到第三次的时候，out和in相遇在D节点，所以D节点时单链表的环入口。

--------------------

今天关于单链表是否有环以及环入口的问题就分享到这里了，提供了四种解法，第一种解法不太友好也不太合理，第二中解法时间复杂度太高，第三种解法空间复杂度太高，第四种解法可能时目前的最优解法了，希望对大家有所帮助。

--------------------

喜欢这篇文章的朋友，欢迎长按下图关注公众号**lebronchen**，第一时间收到更新内容。  
![扫码关注][70]

[E5_8D_95_E9_93_BE_E8_A1_A81.png]: /images/20220517/cbc773ac284849dbbba638a0a5682fe4.png
[2]: /images/20220517/54dac12b19b64f7ebaccc6afc53a967e.png
[3]: /images/20220517/c3c8b716a07647369b7beb74714f8b9d.png
[4]: /images/20220517/0bb9a22f406044d0a65a47b980a80be5.png
[70]: /images/20220517/35c034da1ad44ecca4c32fa4e03318c5.png