单链表环入口方法证明

单链表环入口方法证明

做过单链表找到环入口题目的同学都知道，找到环入口的方法是：

1. 先给定两个指针为low,fast,low每次走一步，fast每次走两步，若有环存在必会走到low == fast。
2. 当low == fast，fast指针指向头结点，然后fast和low每次都各走一步，相遇点即位环入口点。

之前觉得这个算法好牛B啊，想到的是真大神，那为什么这个算法就可以呢，我们来证明一下。

不好意思盗图了，图来自于博主。

好，接下来，我们来证明。

如图所示，我们假设链起点到环入口点的距离为x,环入口点到第一次相遇点的距离为y，在fast指针和low指针相遇时，假设fast已经环n周,此时low走的步数为s，因为fast移动的步数为low的两倍，则fast走的步数为2s，环长为r。

1. s + nr = 2s, (n > 0)
2. s = x + y

由1.可得s = nr，将其带入2.得 x = nr - y

此时来具体说明一下：

现在让指针fast从链表头开始走，指针low从相遇点开始走，它们的步长都为1。当fast走到环入口点，即走了x步，low也走了x步，由于low是从相遇点开始走的，nr步表示low走回到了相遇点，-y步相当于回退了y步，即退到了入口点。证毕。