Java判断单链表是否有环的两种实现方法

大家好，又见面了，我是你们的朋友全栈君。

package learn.linkTest;

import java.util.HashMap;

/**
 * 
 * @author liuxin
 * @date   2018年6月15日
 */


public class LinkLoop {
	private Node root;
	
	public static void main(String[] args) {
		//1-5创建一个无环链表
		Node n1 =new Node(1);
		Node n2 =new Node(2);
		Node n3 =new Node(3);
		Node n4 =new Node(4);
		Node n5 =new Node(5);
		//下面注释的两行为有环链表
//		Node n5 =new Node(1);
//		Node n6 =new Node(5);
		//指定每个节点的下一个节点的值
		n1.next=n2;
		n2.next=n3;
		n3.next=n4;
		n4.next=n5;
//		n5.next=n6;
//		n5.next=n1;
		
		System.err.println(hasLoop(n1));//打印结果是false表示是无环链表，ture是有环链表
		System.err.println(hasLoop2(n1));
		//遍历打印整个链表
		System.out.println(n1.name);
		/**
		 * 不是环时，可调用此方法
		 */
//		while(n1.next!=null){
//			System.out.println("-->"+n1.next.getName());
//			n1=n1.next;
//		}
	}
	
	public void add(int name){
		Node newNode=new Node(name);
		if(this.root==null){
			this.root=newNode;
		}else{
			this.root.addNode(newNode);
		}
	}
	
	public void print(){
		if(this.root!=null){
			this.root.printNode();
		}
	}
	
	/**
	 *方法一： 遍历链表，创建两个类似指针的变量，一个指针每次向后移动一个节点，一个指针每次移动两个节点，如果遇到两者相同的情况说明存在环
	 * @param n
	 * @return
	 */
	public static boolean hasLoop(Node n){
		Node tmp1=n;
		Node tmp2=n.next;
		while (tmp2!=null) {
			if(tmp1==tmp2)return true;
			tmp1=tmp1.next;
			tmp2=tmp2.next.next;
			if(tmp2==null)return false;
		}
		return true;
	}
	/**
	 * 方法二：把每个节点放到hash表中，因为存入的是对象，所有相同的就说明有环
	 * @param n
	 * @return
	 */
	public static boolean hasLoop2(Node n){
		Node tmp1=n;
		HashMap<Node, Node> ns	=new HashMap<Node,Node>();
		while(n!=null){
			if(ns.get(tmp1)!=null)return true;
			ns.put(tmp1, tmp1);
			tmp1=tmp1.next;
			if(tmp1==null)return false;
		}
		return true;
	}
	
	/**
	 * 自建内部类---链表类
	 *
	 * @author liuxin
	 * @date   2018年6月15日
	 */
	static class Node{
		private int name;//名字，用于标识每个节点的名称
		private Node next;//当前节点的下一个节点，也作为自身的一个属性
		public Node(int name){ //构造函数
			this.name = name;
		}
		public int getName(){
			return this.name;
		}
		/*
		 * 增加下一个节点，
		 */
		public void addNode(Node newNode){
			if(this.next == null){
				this.next=newNode;
			}else{
				this.next.addNode(newNode);
			}
		}
		
		public void printNode(){
			System.out.println(this.name+"-->");
			if(this.next!=null){
				this.next.printNode();
			}
		}
	};
		
}

方法一：首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID，则说明该节点被遍历过两次，链表有环；如果之前的所有节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。

例如这样的链表：A->B->C->D->B->C->D， 当遍历到节点D的时候，我们需要比较的是之前的节点A、B、C，不存在相同节点。这时候要遍历的下一个新节点是B，B之前的节点A、B、C、D中恰好也存在B，因此B出现了两次，判断出链表有环。

假设从链表头节点到入环点的距离是D，链表的环长是S。D+S是链表总节点数。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)*(D+S)/2 ， 可以简单地理解成 O(N*N)。而此算法没有创建额外存储空间，空间复杂度可以简单地理解成为O(1)。

方法二：首先创建一个以节点ID为键的HashSet集合，用来存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就用新节点和HashSet集合当中存储的节点作比较，如果发现HashSet当中存在相同节点ID，则说明链表有环，如果HashSet当中不存在相同的节点ID，就把这个新节点ID存入HashSet，之后进入下一节点，继续重复刚才的操作。

这个方法在流程上和方法一类似，本质的区别是使用了HashSet作为额外的缓存。

假设从链表头节点到入环点的距离是D，链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(D+S)=D+S，可以简单理解为O(N)。而算法的空间复杂度还是D+S-1，可以简单地理解成O(N)。

方法三：首先创建两个指针1和2（在java里就是两个对象引用），同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。

例如链表A->B->C->D->B->C->D，两个指针最初都指向节点A，进入第一轮循环，指针1移动到了节点B，指针2移动到了C。第二轮循环，指针1移动到了节点C，指针2移动到了节点B。第三轮循环，指针1移动到了节点D，指针2移动到了节点D，此时两指针指向同一节点，判断出链表有环。

此方法也可以用一个更生动的例子来形容：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。

转自：https://blog.csdn.net/jq_ak47/article/details/52739651