链表是否带环以及环的入口点

带环的链表如图所示，最后一个节点存的不是空，而是链表其中一个节点的地址，形成环形链表。

 

如果是单链表，我们遍历一遍最终会走到空，环形链表不会走到空，因此判断链表是否带环我们可以定义两个指针，一个慢指针一次走一步，一个快指针一次走两步。如果快指针走到空了，说明链表不带环，反之两指针相遇，说明链表带坏。

那么可以慢指针一次走一步，快指针一次走多步吗？

如果快指针一次走多步，有可能走了很久才相遇，也有可能永远都不相遇。

快指针步进太大容易跳过慢指针重新追及，会增加相遇时间，最坏的情况也可能不相遇。

怎么求环的入口点？

我们可以设入环前的路程为x，入环后的路程为y，所以慢指针走的总路程为x+y，刚开始快指针走在慢指针前面，相遇说明快指针已经走了n圈了，设环的周长为C，因此快指针走到总路程为x+nC+y。

又因为慢指针一次走一步，快指针一次走两步，所以快指针的总路程是慢指针的二倍。

建立等式2(x + y) = x + nC + y，化简得x = nC - y。

nC作为一个定值，我们把n设为1，即x = C - y。

可以得出图中x的路程和C-y的路程是相等的。现在用一个指向起点，一个指向fast和slow相遇点的指针，两个指针每次各走一步，相遇点就是环的入口点。