要求：給一個(gè)鏈表，若其中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)，否則，輸出null。

思路：
1、第一步，確定一個(gè)鏈表中是否包含環(huán)。定義兩個(gè)指針，一個(gè)指針一次走一步，另一個(gè)指針一次走兩步，如果快指針追上慢指針，那么鏈表就包含環(huán)。
2、第二步，確定環(huán)中節(jié)點(diǎn)的數(shù)目。由于相遇節(jié)點(diǎn)一定在環(huán)中，然后從這個(gè)節(jié)點(diǎn)出發(fā)，一邊繼續(xù)向前移動(dòng)一邊計(jì)數(shù)，但再次回到這個(gè)節(jié)點(diǎn)的時(shí)候，就可以得到環(huán)中節(jié)點(diǎn)數(shù)了。
3、第三步，找到環(huán)中的入口節(jié)點(diǎn)。重新定義兩個(gè)指針A和B，初始都指向頭節(jié)點(diǎn)，先讓A節(jié)點(diǎn)先移動(dòng)環(huán)中節(jié)點(diǎn)數(shù)目的步數(shù)。然后A和B再以相同速度移動(dòng)，直到A和B相遇,相遇的節(jié)點(diǎn)就是環(huán)的入口節(jié)點(diǎn).

/*
 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;
        }
        // 第一步，確定一個(gè)鏈表中包含環(huán)，定義兩個(gè)指針，一個(gè)指針一次走一步，另一個(gè)指針一次走兩步，如果快指針追上慢指針，那么鏈表就包含環(huán)。
        ListNode slow = ListHead;
        ListNode fast = ListHead;
        boolean flag = false;
        // while退出循環(huán)條件：fast走兩步需要先判斷下一步后是否為空，因?yàn)榭罩羔槦o(wú)next
        // fast指針走向了末尾(null)都沒(méi)追上，說(shuō)明不包含環(huán)。
        while(fast.next!=null && fast != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                flag = true;
                break;
            }
        }
        if(!flag){
            return null;
        }else{
            // 第二步，確定環(huán)中節(jié)點(diǎn)的數(shù)目，由于相遇節(jié)點(diǎn)一定在環(huán)中，然后從這個(gè)節(jié)點(diǎn)出發(fā)，一邊繼續(xù)向前移動(dòng)一邊計(jì)數(shù)，但再次回到這個(gè)節(jié)點(diǎn)的時(shí)候，就可以得到環(huán)中節(jié)點(diǎn)數(shù)了。
            int n=1;   // n保留環(huán)內(nèi)的步數(shù)
            fast = fast.next;
            while(slow!=fast){
                n++;
                fast = fast.next;
            }
            // 此時(shí)獲取到環(huán)中的數(shù)目為n
            // 第三步，找到環(huán)中的入口節(jié)點(diǎn)，重新定義兩個(gè)指針A和B，初始都指向頭節(jié)點(diǎn)，先讓A節(jié)點(diǎn)先移動(dòng)環(huán)中節(jié)點(diǎn)數(shù)目的步數(shù)。然后A和B再以相同速度移動(dòng)，直到A和B相遇,相遇的節(jié)點(diǎn)就是環(huán)的入口節(jié)點(diǎn).
            fast= ListHead;
            slow= ListHead;
            // fast先走n步
            for(int i=1; i<=n;i++){
                fast= fast.next;
            }
            // 再同時(shí)走，直到fast和slow相遇，此時(shí)為入口節(jié)點(diǎn)，原理如23題
            while(fast != slow){
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    }
}