题解 | #链表中环的入口结点#

根据题干，需要完成的任务如下

1. 判断链表是否有环。
2. 在有环的链表中找到环的入口。

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    //判断链表是否存在循环
    public boolean hascucle(ListNode head){
        if(head==null){
            return false;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow==fast){
                return true;
            }
        }
        return false;
    }
    //设快慢两个链表节点，设入口处与遇见处之间的距离为y;
    //设遇见处与入口处的之间的距离为z;
    //设链表表表头与入口处之间的距离为x;
    //则可得出下列等式
    //2(x+y)=x+y+z+y
    //解得 x = z
    //则利用这个思想编写如下代码：
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if( hascucle(pHead)==true){
            ListNode pre = pHead;//表头
            ListNode fast = pHead;//快指针
            ListNode slow = pHead;//慢指针
            //找到相遇节点
            do{
                fast = fast.next.next;
                slow = slow.next;
            }while(fast!=slow);
            //一个从表头开始走，一个从相遇处开始走
            //由于表头到入口处的距离与相遇处到入口的距离相等
            //则这两链表相遇处为入口位置
            while(pre!=slow){
                slow = slow.next;
                pre = pre.next;
            }
            return pre;
        }
        else{
            return null;
        }
       
    }
}