数据结构和算法-判断单链表是否有环求环的入口地址（java）

问题：如上图的一个链表，如何判断一个链表中是否存在环，以及如何求出环的入口以及何如求出链表的长度。

方案一：利用hash表

首先准备一个hash表如hashMap等，然后从链表头部遍历链表，每次遍历一个节点先判断hashMap中是否存在这个节点，如果不存在就把这个节点放入hashMap中，如果存在证明这个链表是存在环的，并且这个节点就是环的入口。这个应该很好理解，也很好实现。当然这也是方案之一，也是很容易被想到的一种方法。因为使用了hash表，所以时间复杂度基本可以看作为O(n)，因为每次遍历节点都要向hashMap中添加数据，所以空间复杂度也为O(n)。因为这种方法比较简单，所以不再贴出代码案例，下面重点分析一下下面的一种方法（快慢指针法），它的时间复杂度为O(n)，但是空间复杂度可以降到O(1)。

方案二：快慢指针法

1.判断链表是否有环

算法流程：所谓的快慢指针就是有两个指针，初始都指向链的表头部，然后算法开始时慢指针一次向前移动一个节点，快指针一次向前移动两个节点。每次移动后判断两个指针是否指向同一个节点。如果是则说明该表链存在环。如果不是则继续上述操作移动指针，直到慢指针遍历完整个链表，则说明该链表没有环。

证明：慢指针slow=slow->next;快指针fast=fast->next->next;进入链表后快指针一定在慢指针前面，如果链表有环，则二者一定会在环上相遇，（就像两个人在操场跑步，跑的快的一定会在某个地方和跑的慢的相遇）并且会在slow指针绕环走完第一圈之前相遇，因为slow每向前一步，fast向前两步，这表明经过这样一次操作两者距离就缩短1。而且经过多次操作以后两者的距离会逐渐缩小是（…4，3，2，1，相遇）又因为在同一个环中fast和slow之间的距离不会大于换的长度，因此到二者相遇的时候slow一定还没有走完一周（或刚好走完一周）。

2.找出环的入口

从判断链表中是否有环的证明中可以得知当fast和slow相遇时，slow还没有走完链表一周，假设fast已经在环内循环了n(1<= n)圈。假设slow走了s步，则fast走了2s步，又由于fast走过的步数也等于s + n*r（设环的长度为r）则：
（1）2*s = s + n * r
（2）s = n*r
如果假设整个链表的长度是L，入口和相遇点的距离是x，起点到入口点的距离是a，则更具第二步有：
（3）a + x = s = n * r
把n*r换成(n - 1) * r + r后得：
（4）a + x = (n - 1) * r + r
又因为链表的长度(L)=环的长度(r)+头结点到环的入口地址的长度(a)，所以r=L-a替换（4）式中的r得：
（5）a + x =(n - 1) * r + (L - a)
（6）a= (n - 1) * r + (L -a -x)
暂且忽略(n - 1) * r
（6）式中得L -a –x正是两个指针第一次相遇时得节点到环得入口节点得距离。它和链表头头节点到环的入口节点的距离相等。
因此我们可以在两指针相遇时将快指针重新指向链表的头指针，然后让他和慢指针一样一次移动一个节点，当两个节点再次相遇的时候这个相遇时的节点就是环的入口。

3.求出环的长度

找到环的入口地址以后，从环的入口地址向下遍历，直到回到环的入口，遍历的节点的个数就是环的长度；

4.求链表的长度

头结点到环的入口节点的长度好求，在加上环的长度就是链表的长度。

java代码

package a;
/**
 * 	链表节点类
 * @author 硅谷探秘者(jia)
 */
class Node{
	public int data;
	public Node next;
	public Node(int data) {
		this.data=data;
	}
	public Node(Node next,int data) {
		this.data=data;
		this.next=next;
	}
}
public class A3 {
	public static void main(String[] args) {
		/**
		 *  构造链表 15->14->13->12->11->10->9->8->7->6->5->4->3->2->1->8
		 */
		Node n1=new Node(1);
		Node n2=new Node(n1,2);
		Node n3=new Node(n2,3);
		Node n4=new Node(n3,4);
		Node n5=new Node(n4,5);
		Node n6=new Node(n5,6);
		Node n7=new Node(n6,7);
		Node n8=new Node(n7,8);
		Node n9=new Node(n8,9);
		Node n10=new Node(n9,10);
		Node n11=new Node(n10,11);
		Node n12=new Node(n11,12);
		Node n13=new Node(n12,13);
		Node n14=new Node(n13,14);
		Node n15=new Node(n14,15);
		n1.next=n10;
		Node e=cycles(n15);
		if(e!=null) {
			System.out.println("入口地址:"+e.data);
			int length=length(e,e);
			int length2=lengthX(n15,e);
			System.out.println("环的长度："+length);
			System.out.println("链表长度："+(length+length2));
		}else {
			System.out.println("没有成环");
		}
	}
	/**
	 * 	判断链表是否成环，是返回环的入口节点，否则返回null
	 * @param n
	 * @return
	 */
	public static Node cycles(Node n) {
		if(n.next!=null&&n.next.next!=null) {
			Node slow = cycle(n.next,n.next.next);
			if(slow!=null)
				return entrance(n,slow);
			else
				return null;
			
		}else {
			return null;
		}
	}
	/**
	 * 	递归判断是否成环
	 * @param slow 慢指针
	 * @param fast 快指针
	 * @return
	 */
	public static Node cycle(Node slow,Node fast) {
		if(fast==null)
			return null;
		else
			if(slow==fast)
				return slow;
			else
				if(fast.next!=null&&fast.next.next!=null)
					return cycle(slow.next,fast.next.next);
				else
					return null;
	}
	/**
	 * 	寻找入口地址
	 * @param slow
	 * @param fast
	 * @return
	 */
	public static Node entrance(Node slow,Node fast) {
		if(slow==fast) return slow;
		else return entrance(slow.next, fast.next);
	}
	/**
	 * 	计算链表长度
	 * @param n
	 * @param e
	 * @return
	 */
	public static int length(Node n,Node e) {
		n=n.next;
		if(n==e) return 1;
		else return 1+length(n, e);
	}
	/**
	 * 	计算头节点到环的入口的长度
	 * @param n
	 * @param e
	 * @return
	 */
	public static int lengthX(Node n,Node e) {
		if(n==e)
			return 0;
		else 
			return length(n, e);
	}
}