本文共 1987 字，大约阅读时间需要 6 分钟。
给定一个单链表，判断其中是否有环，已经是一个比较老同时也是比较经典的问题，在网上搜集了一些资料，
然后总结一下大概可以涉及到的问题，以及相应的解法。
首先，关于单链表中的环，一般涉及到一下问题：
1.给一个单链表，判断其中是否有环的存在；
2.如果存在环，找出环的入口点；
3.如果存在环，求出环上节点的个数；
4.如果存在环，求出链表的长度；
5.如果存在环，求出环上距离任意一个节点最远的点（对面节点）；
6.（扩展）如何判断两个无环链表是否相交；
7.（扩展）如果相交，求出第一个相交的节点；
下面，我将针对上面这七个问题一一给出解释和相应的代码。
对于这个问题我们可以采用“快慢指针”的方法。就是有两个指针fast和slow，开始的时候两个指针都指向链表头head，然后在每一步操作中slow向前走一步即：slow = slow->next，而fast每一步向前两步即：fast = fast->next->next。
由于fast要比slow移动的快，如果有环，fast一定会先进入环，而slow后进入环。当两个指针都进入环之后，经过一定步的操作之后二者一定能够在环上相遇，并且此时slow还没有绕环一圈，也就是说一定是在slow走完第一圈之前相遇。
slow每次向前走一步，fast向前追了两步，因此每一步操作后fast到slow的距离缩短了1步，这样继续下去就会使得
两者之间的距离逐渐缩小：...、5、4、3、2、1、0 -> 相遇。又因为在同一个环中fast和slow之间的距离不会大于换的长度，因此
到二者相遇的时候slow一定还没有走完一周（或者正好走完以后，这种情况出现在开始的时候fast和slow都在环的入口处）。
// 检测环 public static boolean checkCircle(Node list) { if (list == null) return false; Node fast = list,slow = list; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (slow == fast) return true; } return false; } 思路：
如果单链表有环，当slow指针和fast指针相遇时，slow指针还没有遍历完链表，而fast指针已经在环内循环n（n>=1）圈了，假设此时slow指针走了s步，fast指针走了2s步，r为fast在环内转了一圈的步数，a为从链表头到入口点的步数，b为从入口点到相遇点的步数，c为从相遇点再走c步到达入口点，L为整个链表的长度。slow指针走的步数：
s = a + b fast指针走的步数： 2s = s + n*r 即：s = n*r 链表的长度： L = a + b + c = a+r 由上可得： a + b = n*r = (n - 1)*r + r 而r = L - a，所以： a + b = (n - 1)*r + L - a a = (n - 1)*r + L - a - b 而L - a - b = c，所以： a = (n -1)*r +c 综上可得：从链表头到环入口点等于(n - 1)循环内环 + 相遇点到环入口点，于是在链表头和相遇点分别设置一个指针，同时出发，每次各走一步，它们必定会相遇，且第一次相遇的点就是环入口点。//找到环入口点 public static Node findLoopPoint(Node list) { if (list == null) return null; Node fast = list,slow = list; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (slow == fast) break; } if(fast == null || fast.next == null){ return null; } //如果有环，slow指向连表头，此时fast指向相遇点 slow = list; while (slow != fast){ slow = slow.next; fast = fast.next; } return slow; }
转载地址：http://xobii.baihongyu.com/