java如何确定一个链表有环及入口节点

如何确定一个链表有环，入口节点是什么？

1.首先定义一个单链表；

var ，next,是单链表中的属性，分别表示节点值和下一个节点的指向；
代码如下：

				?

									//定义一个链表

									  class  List{

									    public  int var;

									    public  List next;

									//有参构造

									    public List(int var) {

									        this.var = var;

									    }

									//无参构造

									    public List() {

									    }

									    //创建一个带环的链表

									    public  List Create(){

									        List a = new List(1);

									        List b = new List(2);

									        List c = new List(3);

									        List d = new List(4);

									        List e = new List(5);

									        List f = new List(6);

									        a.next = b;

									        b.next =c;

									        c.next = d;

									        d.next =e;

									        e.next = f;

									        f.next =d;

									        return  a;

									    }

2.编写判断是否存在环

如果存在，则返回这个节点，如果不存在则返回null,定义快慢指针，如果快的追上了慢的指针，那么这个链表必存在环，如果没有追上，或者都为null，那么这个链表没有环；
代码如下：

				?

									//判断是否有环，并找到相遇的节点

									public  List MeetingNode(List node){

									    List slow = new List();

									    List fast = new List();

									    if(node==null) return  null;

									    slow = node.next;

									    if(slow==null) return  null;

									    fast=slow.next;

									    while (fast!=null && slow!=null){

									        if (fast==slow){

									            return fast; //fast追上了slow，确定是一个有环的链表；

									        }

									        slow = slow.next;

									        fast = fast.next;

									        if(fast!=null){

									            fast = fast.next;

									        }

									    }

									   return null;

									}

3.寻找入口节点

先让快指针先走环的节点的个数步，在让慢指针开始走，如果两个指针相遇的话，那么相遇的节点必然是环的入口节点
代码如下：

				?

									  public  List Enterdear(List node){

									        if(node==null) return null;

									        if(MeetingNode(node)==null) return null;

									        int count =1;

									        List res2;

									        List res1 = MeetingNode(node);

									        while (res1.next!=MeetingNode(node)){

									            res1 = res1.next;

									            count++;

									        }

									        res1 = node;

									        for(int i = 0;i<count;i++){

									            res1 =res1.next;

									        }

									        res2 = node;

									        while (res1!=res2 && res1!=null && res2!=null){

									            res1 = res1.next;

									            res2 = res2.next;

									        }

									        return res1;

									    }

									}

main函数测试；

				?

									ublic class Deom {

									    public static void main(String[] args) {

									       List SB = new List();

									       List res = SB.Create();

									       List dear= SB.Enterdear(res);

									       System.out.println(dear.var);

									    }

									}