本文主要是介绍[笔试题]判断链表是否有环及环的位置问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
首先，这个问题的最简单情况就是判断两个链表是否相交问题。我写过一篇文章，见这里：http://hi.baidu.com/microgrape/blog/item/5575771e6d3f9c03304e15d8.html
===============================================================
然后引申到如何判断一个链表存在环的问题。
关于这个问题，解决方案及解释如下：
关于这个解法最形象的比喻就是在操场当中跑步，速度快的会把速度慢的扣圈.
可以证明，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点相遇！
==========================================================
这篇关于[笔试题]判断链表是否有环及环的位置问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
