24_链表中环的入口节点

要求：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路：
1、第一步，确定一个链表中是否包含环。定义两个指针，一个指针一次走一步，另一个指针一次走两步，如果快指针追上慢指针，那么链表就包含环。
2、第二步，确定环中节点的数目。由于相遇节点一定在环中，然后从这个节点出发，一边继续向前移动一边计数，但再次回到这个节点的时候，就可以得到环中节点数了。
3、第三步，找到环中的入口节点。重新定义两个指针A和B，初始都指向头节点，先让A节点先移动环中节点数目的步数。然后A和B再以相同速度移动，直到A和B相遇,相遇的节点就是环的入口节点.

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode ListHead){
        if(ListHead == null){
            return null;
        }
        // 第一步，确定一个链表中包含环，定义两个指针，一个指针一次走一步，另一个指针一次走两步，如果快指针追上慢指针，那么链表就包含环。
        ListNode slow = ListHead;
        ListNode fast = ListHead;
        boolean flag = false;
        // while退出循环条件：fast走两步需要先判断下一步后是否为空，因为空指针无next
        // fast指针走向了末尾(null)都没追上，说明不包含环。
        while(fast.next!=null && fast != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                flag = true;
                break;
            }
        }
        if(!flag){
            return null;
        }else{
            // 第二步，确定环中节点的数目，由于相遇节点一定在环中，然后从这个节点出发，一边继续向前移动一边计数，但再次回到这个节点的时候，就可以得到环中节点数了。
            int n=1;   // n保留环内的步数
            fast = fast.next;
            while(slow!=fast){
                n++;
                fast = fast.next;
            }
            // 此时获取到环中的数目为n
            // 第三步，找到环中的入口节点，重新定义两个指针A和B，初始都指向头节点，先让A节点先移动环中节点数目的步数。然后A和B再以相同速度移动，直到A和B相遇,相遇的节点就是环的入口节点.
            fast= ListHead;
            slow= ListHead;
            // fast先走n步
            for(int i=1; i<=n;i++){
                fast= fast.next;
            }
            // 再同时走，直到fast和slow相遇，此时为入口节点，原理如23题
            while(fast != slow){
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    }
}