如何判断单链表是否有环？

引言：单链表是否有环是常见的笔试、面试题，也可能是解决其他方法的一条路径。

问题描述：

1、如何判断单链表是否有环？

2、如何计算环的长度？

3、如何找到环入口节点？

4、如何计算该带环单链表的长度？

一、如何判断单链表是否有环

方法：使用两个指针P1、P2，分别从头部开始遍历，P1每次前进1步，P2每次前进2步，如果单链表中存在环，则P1和P2指针会相遇在环中某点，如果不存在环，则P2提前遇到NULL，程序结束。

对于上图而言，P2每前进2步，P1只前进1步，由图分析可知，P1、P2相遇在链表环中的A点，A点记为相遇点或碰撞点。

二、如何计算环的长度

方法：在碰撞点继续让P1指针和P2指针移动，即P1每移动1步、P2则移动2步，当P1、P2再次碰撞时，P1所走的步数即为该单链表环的长度。

三、如何找到环入口节点

方法一：

设环入口节点为a，头结点到环入口节点长度为A，a点到首次碰撞点距离为X，即上述P1、P2相遇点，环的长度为R，链表总长度为L，假设P1走了S步，则P2走了2S步，并且P2多走了N个环的长度，所以有下列式子：

①2S=S+NR（P2在环上循环，多走了N个R）所以S=NR

②A+X=S（A+X即为P1所走的长度S）

由①②可知，A+X=S=NR=(N-1)R+R=(N-1)R+(L-A)

所以，A=(N-1)R+(L-A-X)，其中L-A-X即为碰撞点X到环入口点A的距离，而(N-1)R记为重复走环N-1圈，当走0圈时，头结点到A结点的距离即为碰撞点X到环入口A点的距离。

综上，使用两个指针X1，Y1，X1指向头结点，Y1指向碰撞点X，X1和Y1同时遍历，当遍历到同一节点时，即X1=Y1时，即为环入口节点A。

注：上图给了实际数字为本链表对应情况，可自行计算验证。

方法二：以环入口节点位置，断开该环，成为一个无环单链表，记环长度为n，则该无环单链表的倒数第n个节点即为环入口节点。倒数第n个节点如何求到：设链表长度为L，使用一个指针P1遍历到L-n处，使用另一个指针P2和此时的P1同时遍历，当P1遍历到最后一个节点时，P2此时指向的便是倒数第n个节点。

四、如何计算带环的单链表长度

方法：二中计算了环的长度，三中计算了头结点到环入口节点的距离，二者相加，即为该单链表的长度。

五、总结

判断单链表是否有环，使用了快慢指针。查找环入口节点中，通过数学计算，发现碰撞点到环入口节点的距离与头结点到环入口节点距离相等，同时也可以使用拆除环的方法，计算倒数第n个节点，但要记住保存破坏的位置，以便恢复。