/**
 * 	链表节点类
 * @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);
	}
}