单链表是否有环--Java

题目：判断一个带头结点的单链表L是否有环 解题思路： 咋看之下，这题还真不好解，于是又一些投机取巧的人，在访问单链表中元素的时候，用一个比较大的数N控制访问元素的个数，他们认为如果在访问到第N个元素之前有一个元素为null，那么单链表没有环，反之，单链表有环。他们的解释是都访问了这么多元素了，还没有一个元素为空，单链表很有可能有环，再加上一般单链表中的元素都不超过N个，所以单链表有环。对于这种解答方式，我们也只能呵呵了。

要判断单链表有没有环，肯定会判断两个指针是否相等。而且这两个指针从头结点位置开始走的步数肯定不一样。可以设两个指针slow，fast，slow从头结点开始往后走，每次走一步，同时fast从头结点开始往后走，每次走两步，这两个指针一直往后面走直到fast为空，则单链表无环，或者slow与fast相等，则单链表有环。这个过程可以保证slow会走过所有在它之前的结点，同时fast比slow多走的步长从1开始每次递增1，而且当它们相遇时多走的步长就是环中结点的个数的正整数倍。

ADT定义：

[java]  view plain  copy //单链表的结点类   class LNode{       //为了简化访问单链表,结点中的数据项的访问权限都设为public       public int data;       public LNode next;   }   算法实现：

[java]  view plain  copy public class LinkListUtli {       public static boolean hasCircle(LNode L)       {           if(L==null) return false;//单链表为空时，单链表没有环           if(L.next==null) return false;//单链表中只有头结点，而且头结点的next为空，单链表没有环           LNode p=L.next;//p表示从头结点开始每次往后走一步的指针           LNode q=L.next.next;//q表示从头结点开始每次往后走两步的指针           while(q!=null) //q不为空执行while循环           {               if(p==q) return true;//p与q相等，单链表有环               p=p.next;               q=q.next.next;           }           return false;       }   }  

拓展：判断带头结点的单链表是否有环，并找出环的入口结点

解题思路：

不妨设从头结点到环的入口结点需要走a步即环外包括头结点在内总共有a个结点，环中有b个结点，假设slow走了s步后，slow与fast第一次相遇。它们肯定是在环内相遇，而且相遇时slow没有从环的入口结点再次走到环的入口结点,假设在环中距离环入口结点d步长距离相遇，设相遇结点为meet。

此时令头结点指向fast，让slow与fast每次往后走一步，当它们再次第一次相遇时，相遇的结点就是环的入口结点。

证明如下：

当slow再走s步后会再次到meet结点，而此时fast走了s步后也会首次到达meet结点，它们相遇，因为两者都是每次同时走一步，那么从fast进入环中开始，fast与slow就一直相遇，它们首次相遇的结点就是环的入口结点。

[java]  view plain  copy public class LinkListUtli {       //当单链表中没有环时返回null，有环时返回环的入口结点       public static LNode searchEntranceNode(LNode L)       {           if(L==null) return null;//单链表为空时，单链表没有环           if(L.next==null) return null;//单链表中只有头结点，而且头结点的next为空，单链表没有环           LNode p=L.next;//p表示从头结点开始每次往后走一步的指针           LNode q=L.next.next;//q表示从头结点开始每次往后走两步的指针           while(q!=null) //q不为空执行while循环           {               if(p==q) break;//p与q相等，单链表有环               p=p.next;               q=q.next.next;           }           if(q==null) return null;              //这里之所以没有向上面一样，先让p,q走一步再进入循环判断，是因为头结点可能就是环的入口结点           q=L;           while(q!=null)           {               if(p==q) return p;//返回环中入口结点               p=p.next;               q=q.next;           }           return null;       }   }  

拓展：判断带头结点的单链表是否有环，并求环的长度

解题思路：

设一个指针q指向环入口结点，让q往后移动直到q再次等于环的入口结点，此时q所走的总步数就是环的长度

[cpp]  view plain  copy public class LinkListUtli {       //当单链表中没有环时返回null，有环时返回环的入口结点       public static LNode searchEntranceNode(LNode L)       {           if(L==null) return null;//单链表为空时，单链表没有环           if(L.next==null) return null;//单链表中只有头结点，而且头结点的next为空，单链表没有环           LNode p=L.next;//p表示从头结点开始每次往后走一步的指针           LNode q=L.next.next;//q表示从头结点开始每次往后走两步的指针           while(q!=null) //q不为空执行while循环           {               if(p==q) break;//p与q相等，单链表有环               p=p.next;               q=q.next.next;           }           if(q==null) return null;              //这里之所以没有向上面一样，先让p,q走一步再进入循环判断，是因为头结点可能就是环的入口结点           q=L;           while(q!=null)           {               if(p==q) return p;//返回环中入口结点               p=p.next;               q=q.next;           }           return null;       }              //求单链表环的长度       public static int circleLength(LNode L)       {           LNode p=searchEntranceNode(L);//找到环的入口结点           if(p==null) return 0;//不存在环时，返回0           LNode q=p.next;           int length=1;           while(p!=q)           {               length++;               q=q.next;           }           return length;//返回环的长度       }   }