导读：额，我介绍的这两种方法，有点蠢啊，小打小闹的那种，后来我查了查资料，别人都起了好高大上的名字，不过，本篇博客，我还是用何下下的风格来写。两种方法，一种是丢手绢法，另外一种，是迷路法。
这两种方法的基本思想：假设有环（顿时想到了三个数中找最大的，假设一个最大值有木有，更有木有想到一个排序算法呢？）
一、丢手绢法（指针追赶法）
其实，这种方法时有个很高大上的名称的，叫做指针追赶法。不过，我刚开始想了半天没想明白，后来等我想明白了之后，哇塞，其实思想就是我小时候玩得丢手绢的游戏。
趣说指针追赶法：想象一下小时候玩丢手绢，自己是怎么死的？你妹的，就一个圈，往一个方向跑，自己跑的比别人慢，还没跑几步，然后就被追上了。反例：要是这不是一个圈，咱俩从一个地方往一个方向跑，你老人家跑的比我快，能追上不？（PS：想不明白的，就往死了想玩丢手绢是怎么死的。短跑健将抓小偷，是怎么跑到小偷前面被小偷嘲笑的）
好了，思想说完了，看看代码：
public class stringTest {
/**
* 内部类，模拟链表
* @author AngelHHX
*
*/
public static class Node{
int value;
Node next;
public Node(int n){
this.value=n;
this.next=null;
}
}
public static boolean hasLoop(Node n){
//定义两个指针，一个每次走一步，一个每次走两步
Node Point1=n;
Node Point2=n.next;
while(Point2!=null){
Point1=Point1.next;//每次走一步
Point2=Point2.next.next;//每次走两步
if(Point2==null) return false;//不存在环
int value1=Point1.value;
int value2=Point2.value;
if(value1==value2) return true;//存在环
}
return false;//当Point2为null，证明这个链表中只有一个元素
}
public static void main(String[] agrs) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
n1.next = n2;
n2.next = n3;
n3.next = n1;//构造一个带环的链表,去除此句表示不带环
System.out.println(hasLoop(n1));
}
}
二、迷路法（查表法）
这个方法的基本思想，真的跟我这个人有关，想明白这个方法的内涵，只需要我自己出门走一圈就OK了！ 题外话啊，有小时候看过《少年包青天》的不？里面有一集，就是展昭中毒的那一集，然后公孙策和香香走进了一个树林里，她俩迷路了，然后香香扯那个裙子绑树上打标记，结果走着走着就又回到了原地！
额，想想自己迷路的时候，如果你发现你走了好久，结果又回到了某一个地方，内心崩溃：我他妈的走了半天，竟然还在原地打圈圈！（反正我是这样的）然后再想想数据结构中图的简单回路那一节内容，好好体会吧。
简单说来，就是将指针每走的一个节点记录下来，然后每次走一个节点，就去记录里面查，如果发现重复了，那么恭喜你，迷路了。（链表有环）
代码如下：
import java.util.HashMap;
public class stringTest {
/**
* 内部类，模拟链表
* @author AngelHHX
*
*/
public static class Node{
int value;
Node next;
public Node(int n){
this.value=n;
this.next=null;
}
}
public static boolean hasLoop(Node n){
Node Point1=n;
HashMap<Node,Node> HM=new HashMap<Node,Node>();
while(n!=null){
if(HM.get(Point1)!=null) return true;
else HM.put(Point1, Point1);
Point1=Point1.next;
if(Point1==null) return false;
}
return false;
}
public static void main(String[] agrs) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
n1.next = n2;
n2.next = n3;
n3.next = n1;//构造一个带环的链表,去除此句表示不带环
System.out.println(hasLoop(n1));
}
}
三、总结
以上就是关于是否有环的判断，突然有一种感觉，生活远远比写代码复杂的多！写代码真的跟生活经历有关，好好去体验生活，去经历，真的会很好！接下来的工作，就是把我草稿箱的那些要写的博客都写完，然后看看书！
对于java基础的东西，尤其是数据结构和算法方面的，自己真心比较弱，还请大家多多指教！PS：我这么一直看书，一直总结，在做项目的时候，再思考思考，有没有感觉到，我这是下次考数据结构，必过的节奏啊。。。。。。。。。。