剑指Offer-链表中环的入口

链表中环的入口

题目

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

思路

先找到环，再把快结点拨回头，和slow相遇的地方就是入口

代码

    public class EntryNodeOfLoop {
    public class ListNode{
        int val;
        ListNode next = null;
        ListNode(int val){
            this.val = val;
        }

    }
    public ListNode EntryNodeOfLoop(ListNode pHead){

        if (pHead==null||pHead.next==null){
            return null;
        }

        ListNode fast = pHead;
        ListNode slow = pHead;

        while (fast!=null&&slow!=null){
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast){//存在环
                fast = pHead;
                while (slow !=fast){//走到一样的地方就是环的入口点
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }

        return null;
    }
}