判断单链表中是否有环，找到环的入口节点

 

这类问题通常使用双指针的方法，即一个快指针一个慢指针。

faster = faster.next.next;

slower = slower.next;

“公理”：两指针相遇时，快指针走过的路程为慢指针的2倍。

链表有环时，有以下3种情况，右边和下边都是第一种的特例，下文以第一种为讨论对象。

1.判断是否有环

两个指针开始时均指向头节点，快指针每次跨2个节点，慢指针每次跨1个节点。判断逻辑如下；

1. while (faster.next != null && faster.next.next != null) {

2. faster = faster.next.next;

3. slower = slower.next;

4. if (faster == slower) {

5. return true;

6. }

7. }

8. return false;

 

2.求环的长度

假设两个指针在b点相遇。则点b必在环中，以b点为出发点，两个指针再来一次“追逐”，慢指针走一圈，快指针走2圈后他们又在b点相遇。此时慢指针走过的路程即为环周长。

3.求环入口

根据前文的“公理”可得：a+nr+b=2(a+b),  其中r为圆周长，n>=1

化简得：a=nr-b, 即: a=(n-1)r+r-b

这个式子的意义就是，一个慢指针slower1从链表头出发，1个慢指针slower2从b点出发，slower1走到环入口时(路程为a)，slower也刚好走到环入口（路程为(n-1)r+r-b：n-1个整圈加上r-b的路程)

所以求环的入口算法为：

1. Node meet = null;

2. while (faster.next != null && faster.next.next != null) {

3. faster = faster.next.next;

4. slower = slower.next;

5. if (faster == slower) {

6. meet = faster;

7. }

8. }

9.  

10. if (meet != null) {

11. newSlower = head;

12. while (newSlower != slower) {

13. newSlower = newSlower.next;

14. slower = slower.next;

15. }

16. return newSlower;

17. }

18. return null;

 

参考：

https://www.cnblogs.com/byrhuangqiang/p/4708608.html

https://blog.csdn.net/u011373710/article/details/54024366

转载：https://blog.csdn.net/u011250186/article/details/101314130