連結清單中環的入口結點（劍指offer）

給一個連結清單，若其中包含環，請找出該連結清單的環的入口結點，否則，輸出null。

方法一：雙指針

分析：首先用雙指針就能探測對外連結表是否有換，如果有環，兩個指針肯定會相遇 的。

a是頭結點到入口結點的距離，b是入口節點Y到相遇處Z的距離，c是環的長度減去b。

相遇時有：

S_{fast} = 2S_{slow}

假設相遇時pFast在環内轉了k圈，則

a + k(b+c) + b = 2(a + b) 

移項得：

a = (k-1)(b+c) + c

說明頭結點X到入口結點Y的距離等于從相遇處Z開始在環内轉悠k-1圈（k >= 1）後，最後從Z到Y的距離。當k =1時候，a = c，此時pFast比pSlow多走一圈

/*
 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;
        ListNode fast=pHead;
        while (fast!=null||fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                fast=pHead;
                while (slow!=fast){
                    fast=fast.next;
                    slow=slow.next;
                }
            }
            if(slow==fast)
                return fast;
        }
        return null;
    }
}      

轉載于:https://www.cnblogs.com/shaer/p/10718036.html