给定一个单链表，判断其中是否有环，已经是一个比较老同时也是比较经典的问题，在网上搜集了一些资料，
然后总结一下大概可以涉及到的问题，以及相应的解法。
首先，关于单链表中的环，一般涉及到一下问题：
1.给一个单链表，判断其中是否有环的存在；
2.如果存在环，找出环的入口点；
3.如果存在环，求出环上节点的个数；
4.如果存在环，求出链表的长度；
5.如果存在环，求出环上距离任意一个节点最远的点（对面节点）；
6.（扩展）如何判断两个无环链表是否相交；
7.（扩展）如果相交，求出第一个相交的节点；
下面，我将针对上面这七个问题一一给出解释和相应的代码。
问题1.判断是否有环（链表头指针为head）
对于这个问题我们可以采用“快慢指针”的方法。就是有两个指针fast和slow，开始的时候两个指针都指向链表头head，然后在每一步操作中slow向前走一步即：slow = slow->next，而fast每一步向前两步即：fast = fast->next->next。由于fast要比slow移动的快，如果有环，fast一定会先进入环，而slow后进入环。当两个指针都进入环之后，经过一定步的操作之后，二者一定能够在环上相遇，并且此时slow还没有绕环一圈，也就是说一定是在slow走完第一圈之前相遇。
代码：
/**
* 1.判断是否有环
* 对于这个问题我们可以采用“快慢指针”的方法。就是有两个指针fast和slow，开始的时候两个指针都指向链表头head，然后在每一步
* 操作中slow向前走一步即：slow = slow->next，而fast每一步向前两步即：fast = fast->next->next。
* 由于fast要比slow移动的快，如果有环，fast一定会先进入环，而slow后进入环。当两个指针都进入环之后，经过一定步的操作之后
* 二者一定能够在环上相遇，并且此时slow还没有绕环一圈，也就是说一定是在slow走完第一圈之前相遇。
* @param head
* @return
*/
public boolean isHasLoop(Node head){
Node fast = head;
Node slow = head;
while(slow != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
//有环
return true;
}
}
//无环
return false;
}
问题2.如果存在环，找出环的入口点；
我结合着下图讲解一下：
从上面的分析知道，当fast和slow相遇时，slow还没有走完链表，假设fast已经在环内循环了n(1<= n)圈。环的长度为r， 假设slow走了s步，s=a+b,其中：a为从head到环入口点的长度，b为从环入口点到相遇点的长度，则fast由于每次比slow多走一步，则共走了2s步， 同时相当于比slow多走了n圈环，即共走了：s + n*r步，即：
a+b+nr = 2(a+b)
化简得：a=nr-b, 即: a=(n-1)r+r-b
这个式子的意义就是，一个慢指针slow1从链表头出发，1个慢指针slow2从相遇点，即b点出发，slow1走到环入口时(路程为a)，slow2也刚好走到环入口（路程为(n-1)r+r-b：n-1个整圈加上r-b的路程)
/**
* 2.如果存在环，找出环的入口点
* 从上面的分析知道，当fast和slow相遇时，slow还没有走完链表，假设fast已经在环内循环了n(1<= n)圈。环的长度为r
* 假设slow走了s步，s=a+b,其中：a为从head到环入口点的长度，b为从环入口点到相遇点的长度，则fast由于每次比slow多走一步，则共走了2s步，
* 同时相当于比slow多走了n圈环，即共走了：s + n*r步，即：
*
* a+b+nr = 2(a+b)
* 化简得：a=nr-b, 即: a=(n-1)r+r-b
*
* 这个式子的意义就是，一个慢指针slow1从链表头出发，1个慢指针slow2从相遇点，即b点出发，slow1走到环入口时(路程为a)，
* slow2也刚好走到环入口（路程为(n-1)r+r-b：n-1个整圈加上r-b的路程)
*
*
* @param head
* @return
*/
public Node getLoopFirstNode(Node head){
Node meet = null;
Node fast = head;
Node slow = head;
while (fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
meet = fast;
}
}
if (meet != null) {
Node slowFromHead = head;
while (slowFromHead != meet) {
slowFromHead = slowFromHead.next;
meet = meet.next;
}
return slowFromHead;
}
return null;
}
问题3.如果存在环，求出环上节点的个数:
对于这个问题，我这里有两个思路（肯定还有其它跟好的办法）：
思路1：记录下相遇节点存入临时变量tempPtr，然后让slow(或者fast，都一样)继续向前走slow = slow -> next；一直到slow == tempPtr; 此时经过的步数就是环上节点的个数；
思路2： 从相遇点开始slow和fast继续按照原来的方式向前走slow = slow -> next; fast = fast -> next -> next；直到二者再次项目，此时经过的步数就是环上节点的个数 。
/**
* 3.如果存在环，求出环上节点的个数；
* 对于这个问题，我这里有两个思路（肯定还有其它跟好的办法）：
*
* 思路1：记录下相遇节点存入临时变量tempPtr，然后让slow(或者fast，都一样)继续向前走slow = slow -> next；一直到slow == tempPtr;
* 此时经过的步数就是环上节点的个数；
*
* 思路2： 从相遇点开始slow和fast继续按照原来的方式向前走slow = slow -> next; fast = fast -> next -> next；直到二者再次项目，
* 此时经过的步数就是环上节点的个数 。
*
* @param head
* @return
*/
public int getLoopLength(Node head){
int length = 0;
Node meet = null;
Node fast = head;
Node slow = head;
while (fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
meet = fast;
}
}
if (meet != null) {
Node temp = meet;
do{
meet = meet.next;
length++;
}
while (meet != temp);
}
return length;
}
问题4. 如果存在环，求出链表的长度：
链表长度L = 起点到入口点的距离 + 环的长度r;
已经知道了起点和入口点的位置，那么两者之间的距离很好求了吧！环的长度也已经知道了，因此该问题也就迎刃而解了！
/**
* 4.如果存在环，求出链表的长度；
* 链表长度L = 起点到入口点的距离 + 环的长度r;
* 已经知道了起点和入口点的位置，那么两者之间的距离很好求了吧！环的长度也已经知道了，因此该问题也就迎刃而解了！
*
* @param head
* @return
*/
public int getLinkTableLength(Node head){
int headToLoopFirstNodeLength = 0;
int loopLength = 0;
int linkTableLength = 0;
Node meet = null;
Node loopFirstNode = null;
Node fast = head;
Node slow = head;
while (fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
meet = fast;
}
}
if (meet != null) {
//找出环的第一个节点
Node slowFromHead = head;
while (slowFromHead != meet) {
slowFromHead = slowFromHead.next;
meet = meet.next;
}
//计算环的长度
loopFirstNode = slowFromHead;
do{
slowFromHead = slowFromHead.next;
loopLength++;
}
while (slowFromHead != loopFirstNode);
//从head到环第一个节点的距离
while(head != loopFirstNode){
headToLoopFirstNodeLength++;
}
linkTableLength = headToLoopFirstNodeLength + loopLength;
}
return linkTableLength;
}
问题5. 求出环上距离任意一个节点最远的点（对面节点）
如下图所示，点1和4、点2和5、点3和6分别互为”对面节点“ ，也就是换上最远的点，我们的要求是怎么求出换上任意一个点的最远点。
对于换上任意的一个点ptr0, 我们要找到它的”对面点“，可以这样思考：同样使用上面的快慢指针的方法，让slow和fast都指向ptr0，每一步都执行与上面相同的操作（slow每次跳一步，fast每次跳两步），
当fast = ptr0或者fast = prt0->next的时候slow所指向的节点就是ptr0的”对面节点“。
为什么是这样呢？我们可以这样分析：
如上图，我们想像一下，把环从ptro处展开，展开后可以是无限长的（如上在6后重复前面的内容）如上图。
现在问题就简单了，由于slow移动的距离永远是fast的一般，因此当fast遍历玩整个环长度r个节点的时候slow正好遍历了r/2个节点，
也就是说，此时正好指向距离ptr0最远的点。
/**
* 5.如果存在环，求出环上距离任意一个节点最远的点（对面节点）；
* 对于换上任意的一个点ptr0, 我们要找到它的”对面点“，可以这样思考：同样使用上面的快慢指针的方法，让slow和fast都指向ptr0，
* 每一步都执行与上面相同的操作（slow每次跳一步，fast每次跳两步），
*
* 当fast = ptr0或者fast = prt0->next的时候slow所指向的节点就是ptr0的”对面节点“, 即当fast刚好走一圈时，
* 这个时候fast和slow之间的距离最远，之后距离主键缩小直至相遇。
*
*/
public Node getFarestNode(Node cur){
Node fast = cur;
Node slow = cur;
do{
fast = fast.next.next;
slow = slow.next;
}
while(fast != cur);
return slow;
}
问题6.（扩展）如何判断两个无环链表是否相交，和7（扩展）如果相交，求出第一个相交的节点，
两个链表相交只能是以下两种情况：
a有环，b有环，相交时共享同一个环
a无环，b无环，
第一种相当于分别算出各自环的一个点，如果一样，则相交；
对于第二种无环链表是否相交问题，假设有连个链表listA和listB，如果两个链表都无环，并且有交点，那么我们可以让其中一个链表（不妨设是listA）的为节点连接到其头部，这样在listB中就一定会出现一个环。所以该问题转化为：1.listA构建一个环，2.判断listB是否有环，有则相交，无则不相交
因此我们将问题6和7分别转化成了问题1和2.
看看下图就会明白了：
/**
*
* 6.（扩展）如何判断两个无环链表是否相交；
* 两个链表相交只能是以下两种情况：
* a有环，b有环，相交时共享同一个环
* a无环，b无环，
*
* 第一种相当于分别算出各自环的一个点，如果一样，则相交；
* 对于第二种无环链表是否相交问题，假设有连个链表listA和listB，如果两个链表都无环，并且有交点，那么我们可以让其中一个链表
* （不妨设是listA）的为节点连接到其头部，这样在listB中就一定会出现一个环。所以该问题转化为：1.listA构建一个环，2.判断listB是否有环，
* 有则相交，无则不相交
*
* 因此我们将问题6和7分别转化成了问题1和2.
*
* @param head1
* @param head2
* @return
*/
public boolean isTwoLinkTableIntersect(Node head1, Node head2){
//list1 首尾连起来
Node tail1 = head1;
while(head1.next != null){
tail1 = tail1.next;
}
tail1.next = head1;
//判断list2是否有环
return isHasLoop(head2);
}
/**
* 7.（扩展）如果相交，求出第一个相交的节点
* 其实就是做一个问题的转化：
*
* 假设有连个链表listA和listB，如果两个链表都无环，并且有交点，那么我们可以让其中一个链表（不妨设是listA）的为节点连接到其头部，这样在listB中就一定会出现一个环。
*
* 因此我们将问题6和7分别转化成了问题1和2.
*
* @param head1
* @param head2
* @return
*/
public Node getTwoLinkTableIntersectNode(Node head1, Node head2){
//list1 首尾连起来
Node tail1 = head1;
while(head1.next != null){
tail1 = tail1.next;
}
tail1.next = head1;
return getLoopFirstNode(head2);
}
原地址：http://blog.csdn.net/doufei_ccst/article/details/10578315
