[笔试题]判断链表是否有环及环的位置问题

首先，这个问题的最简单情况就是判断两个链表是否相交问题。我写过一篇文章，见这里：http://hi.baidu.com/microgrape/blog/item/5575771e6d3f9c03304e15d8.html

===============================================================

然后引申到如何判断一个链表存在环的问题。一个有环的链表示意图如下：

注：图中的head是链表头；粗的线条表示链表，其中环从图中O点开始，从链表头到交点的距离为z。P点及另外两个长度下面再解释。

关于这个问题，解决方案及解释如下：

用两个指针来遍历这个单向链表，第一个指针p1，每次走一步；第二个指针p2，每次走两步；当p2 指针追上 p1的时候，就表明链表当中有环路了。

关于这个解法最形象的比喻就是在操场当中跑步，速度快的会把速度慢的扣圈.

可以证明，p2追赶上p1的时候，p1一定还没有走完一遍环路，p2也不会跨越p1多圈才追上.

我们可以从p2和p1的位置差距来证明，p2一定会赶上p1但是不会跳过p1的.

因为p2每次走2步，而p1走一步，所以他们之间的差距是一步一步的缩小，4，3，2，1，0 到0的时候就重合了.

根据这个方式，可以证明，p2每次走三步以上，并不总能加快检测的速度，反而有可能判别不出有环.

比如，在环的周长L是偶数的时候，初始p2和p1相差奇数的时候，p2每次走三步，就永远和p1不重合，因为他们之间的差距是：  5， 3 ， 1，   L－1， L－3

附加几点解释：虽然说p1看来“相对”于p2并不前进，但是“绝对”来说，它还是前进的，那么迟早它会跑到圆圈上，而且不再出来。p2就更是了。所 以，尽管有可能p1还没有进圆圈，p2已经跑完几圈了（想象一下圆圈很小，但是前面的直道部分很长的情况），但是p1迟早要进圈，演变成跑步问题。

========================================================

下面则再进一步：如何判断链表的环开始的位置呢？也就是环与链表的交点。

这个问题就更靠近脑筋急转弯的方向了。首先想到，如果还是p1和p2一起跑圈，那仍然会发生很多次相遇，但是这个相遇跟起点并无关系，想求出入口不可能。

那我们就分析一下，p1和p2相遇的时候到底发生了什么。在示意图中，假设p1和p2在P点第一次相遇。从环路入口到P点的距离为x，从P点到环路入口的另一段的距离为y。

那么显然，第一次相遇的时候，p1走过的总长度为x+z。那p2呢？我们首先假设p2比p1只多跑了一圈（方便理解，但并不影响最后结论，下面再证明所有的情况）。那么容易得到，p2走过的总长度为z+x+y+x。这个结论很显然也是表明p2比p1多跑了一圈（一圈的长度就是x+y，与前面的分析吻合）。由于p2的速度是p1的两倍，很容易得到一个结论：z+x+y+x = 2 * (x+z)。也就是z = y。也就是说，相遇的点离环路入口的距离与链表直道的长度一样。

呵呵，得到这个结论似乎就离我们的答案很近了：如何才能找到这个入口位置呢？显然，让一个指针从相遇的P点出发，另外一个指针从链表头出发，以相同的速度前进，那么它们必然会在O点也就是环路入口相遇！

补充证明：设p2跑了n圈之后，才跟p1相遇（但请注意：p1一定是在自己的第一圈，因为不可能发生两个指针都在圈内，p2超过了p1但是没相遇的情况，前面的分析里说了），那么可以得到下面的等式：

z + n * (x+y) + x = 2 * (x+z)

最后可以得到下面的式子：z = n*(x+y) - x = (n-1)*(x+y) + y。 也就是说直道的长度等于n-1圈的长度加上y的长度，仍然不影响上面的结论：如果两个指针速度相同，一个指针从head出发，另一个从P点出发（跑n-1 圈，再跑y），所花时间相等。它们一定会在O点相遇！

==========================================================