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

一时失言乱红尘 2022-05-24 09:44 225阅读 0赞

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

faster = faster.next.next;

slower = slower.next;

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

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

![20180524213738527][]

1.判断是否有环

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

while (faster.next != null && faster.next.next != null) {
        faster = faster.next.next;
        slower = slower.next;
        if (faster == slower) {
            return true;
        }
    }
    return false;

2.求环的长度

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

3.求环入口

![20180524215151196][]

根据前文的“公理”可得：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的路程)

所以求环的入口算法为：

Node meet = null;
    while (faster.next != null && faster.next.next != null) {
        faster = faster.next.next;
        slower = slower.next;
        if (faster == slower) {
            meet = faster;
        }
    }
    
    if (meet != null) {
        newSlower = head;
        while (newSlower != slower) {
            newSlower = newSlower.next;
            slower = slower.next;
        }
        return newSlower;
    }
    return null;

参考：

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

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

[20180524213738527]: /images/20220524/8d8bdf4558fc4f3eb5919ea45a8fdf92.png
[20180524215151196]: /images/20220524/9bd88acb5e4543a689d05c85f40116cd.png