判断链表是否有环 及 寻找环的入口_链表里怎么找到环的入口

1、思路

链表是否有环：使用快慢指针，快指针每次走两步，慢指针每次走一步，如果如果快指针走到了next指针为null时，则链表无环；如果快慢指针相遇，则链表有环。

寻找环的入口：使用快慢指针，快指针每次走两步，慢指针每次走一步；当快慢指针第一次相遇时，将快指针指向链表头部，并且改成每次走一步；下一次快慢指针相遇的位置，就是环入口位置。

2、证明

链表是否有环：

（1）如果链表无环，则快慢指针不会相遇，快指针一定会走到链表的尾部，也就是next指针为null的地方。

（2）如果链表有环，则快慢指针一定会相遇，证明如下：

          当快慢指针都位于环内时，环是不存在先后之分的，我们可以将快慢指针的相遇，当成快指针追赶慢指针的过程，然后用数据归纳法分情况讨论：

          *1）如果快指针位于慢指针后面1位，则下一次走时，慢指针往前走1位，快指针往前走2位，快慢指针相遇。

          *2）如果快指针位于慢指针后面2位，则下一次走时，慢指针往前走1位，快指针往前走2位，变成*1）的情况。

          *3）如果快指针位于慢指针后面n位，则下一次走时，慢指针往前走1位，快指针往前走2位，快指针位于慢指针后面n-1位。