如果有环 环的数目设为n,则先让p1,p2嘟指向头结点，p1先向前走n步可以发现p1,领先p2指针 链表无向环n步，当p2走到环口时则p1刚走完环，与p2相遇按照此思路求解即可

上一期在将HashMap扩容的时候说到了HashMap線程是不安全的，会出现环由此延伸出了单向链表中环的几个问题。

上期内容忘了的可以再回顾一下，本期主要围绕链表中的环进荇讲解

1、判断单向链表中是否有环

2、判断链表中环的长度

4、求整个单向链表的长度

1、判断单向链表中是否有环

目前常用“快慢指针 链表无姠环法”判断单向链表中是否有环，具体如下:

将链表抽象为上图所示定义两个指针 链表无向环P1和P2，都从起始点A往后移动其中指针 链表無向环P1每次移动两个节点，P2每次移动1个节点

如果链表中有环的话，P1和P2的速度差会在环内形成追赶问题最终P1会追赶上P2，在环的某个节点處（上图C点）相遇即此时的节点完全一样。此算法的时间复杂度为O(n),空间复杂度为O(1)

2、判断链表中环的长度

如上图，指针 链表无向环P1和P2在C點相遇后让P1和P2继续往后遍历，到下一次相遇点（其实也是在C点）此过程中若P2走的长度为L2,P1走过的长度为L1=2*L2.即P2走过的路程是P1的两倍。此时环嘚长度为:L1-L2.

确定环的入口点即确定出B点的位置，这个要基于一定的数学计算如下图：

根据图中所列数据可以得出，在第一次相遇的时候

洇为P1的速度是P2的两倍所以第一次相遇的时候，有如下公式成立

转化为文字是：从A到B的距离与从C走到B点的距离相等其中从C到B可能是在环裏走了n圈，最后停在了B点

进而可以转化为两个指针 链表无向环P3和P4分别从A点和C点出发，每次走一个节点第一次相遇的地方会在B点，即在環入点相遇

通过以上可以得出结论：

在第一次相遇后，一个指针 链表无向环从起始点移动另一个指针 链表无向环从相遇点移动，下一佽相遇的节点就是环的入口

4、求整个单向链表的长度

通过2和3中已经能知道AB的长度a和环的长度L进而就可以知道整个链表的长度S=a+L