链表中环的入口结点

一个链表中包含环，请找出该链表的环的入口结点。

IDEA

1.首先判断链表是否带环。

采用在头结点设两个指针，一个叫fast，一个叫slow，fast一下走两步，而slow一下走一步。如果链表中存在环的话，那么fast和slow必定会在环中相遇。若链表中没有环的话，那么fast必定现于slow指针先到达链表的尾节点（->next = Null）。

2.找出环的入口点。

相遇的时候，slow共移动了s步，fast共移动了2s步。定义a：链表头移动a步到达入口点。定义x：入口点移动x步到达相遇点。定义c：环长度。有2s=s+nc=>s=ncs=a+x=>a+x=nc=>a=nc-x=>a=nc-c+c-x=(n-1)c+(c-x)即c-x为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

2.可以计算环的长度。

再环的入口点设一指针和一计数器，让这一指针在环里面跑，计数器不断自增。当这一指针回到环的入口点的时候，环长就出来啦。

CODE

/* public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/public class Solution {    public ListNode EntryNodeOfLoop(ListNode pHead)    {        if(pHead==null||pHead.next==null)            return null;        ListNode slow=pHead,fast=pHead;        while(fast!=null&&fast.next!=null){            slow=slow.next;            fast=fast.next.next;            if(slow==fast)                break;        }        if(fast==null||fast.next==null)            return null;        slow=pHead;        while(slow!=fast){            slow=slow.next;            fast=fast.next;        }        return slow;    }}