問題描述：

給一個長度為n的鏈表，若其中包含環(huán)，請找出該鏈表的環(huán)的入口結(jié)點(diǎn)，否則，返回null。

數(shù)據(jù)范圍： n≤1000

要求：空間復(fù)雜度 O(1)，時間復(fù)雜度 O(n）

解題思路：

1. hash法

   遍歷所有節(jié)點(diǎn)，將節(jié)點(diǎn)地址依次存儲在一個hash表中，等走完環(huán)形部分回到環(huán)的入口節(jié)點(diǎn)處，此時hash表中已經(jīng)存儲過所有節(jié)點(diǎn)，經(jīng)過判斷是否存在該節(jié)點(diǎn)會返回true，則該節(jié)點(diǎn)就是入口節(jié)點(diǎn)，直接返回即可。

   時間復(fù)雜度：O(n)

   空間復(fù)雜度：O(n)

   該方法因?yàn)榭臻g復(fù)雜度不滿足要求，所以不做重點(diǎn)講解

2. 雙指針法

   初始化兩個節(jié)點(diǎn)指向鏈表頭結(jié)點(diǎn)，一個步進(jìn)快的fast，一個步進(jìn)慢的slow，設(shè)定fast節(jié)點(diǎn)每次步進(jìn)兩步，slow節(jié)點(diǎn)每次步進(jìn)一步。當(dāng)兩個節(jié)點(diǎn)第一次相遇（指向同一個節(jié)點(diǎn)，此時在環(huán)中）的時候，將其中一個節(jié)點(diǎn)重置為指向頭結(jié)點(diǎn)然后分別以一為步長重新步進(jìn)，待兩個節(jié)點(diǎn)重新相遇，則被指向的節(jié)點(diǎn)就為環(huán)的入口節(jié)點(diǎn)。

   時間復(fù)雜度：O(n)

   空間復(fù)雜度：O(1)

   下面著重講解該方法

注意事項(xiàng)：

跳出循環(huán)的判斷條件以及跳出第一次循環(huán)后判斷是否是正常跳出：正常跳出則返回null，表示沒有環(huán)，打斷則繼續(xù)第二個循環(huán)

論證

• 結(jié)論一：兩個節(jié)點(diǎn)第一次相遇一定指向環(huán)中的節(jié)點(diǎn)

  顯然節(jié)點(diǎn)的步進(jìn)速度一快一慢，這里的設(shè)定是快速節(jié)點(diǎn)是慢速節(jié)點(diǎn)速度的兩倍，所以假如鏈表沒有環(huán)，則慢速節(jié)點(diǎn)永遠(yuǎn)無法追上快速節(jié)點(diǎn)與其相遇，所以反推兩節(jié)點(diǎn)能相遇必然鏈表中存在環(huán)并且相遇的節(jié)點(diǎn)只能在環(huán)中。

• 結(jié)論二：重置其中一個節(jié)點(diǎn)指向頭結(jié)點(diǎn)后分別以一為步長重新步進(jìn)，待兩個節(jié)點(diǎn)重新相遇，則被指向的節(jié)點(diǎn)為環(huán)的入口節(jié)點(diǎn)

  image

  （圖片內(nèi)容僅用于抽象說明問題）

  如上圖a：

  |ad|=a，|dg|=b，|gd|=c

  快指針路程=a+（b+c）k+b，k>=1，其中b+c為環(huán)的長度，k為環(huán)的圈數(shù)（k>=1，即最少一圈，不能是0圈，不然快慢指針走的路程一樣，矛盾）。

  慢指針路程=a+b。

  因?yàn)榭熘羔樀穆烦淌锹羔樀穆烦痰膬杀?，所以?strong>（a+b）*2=a+（b+c）k+b。

  化簡得：

  a=（k-1）（b+c）+c，這個式子的意思是：鏈表頭到環(huán)入口的距離=相遇點(diǎn)到環(huán)入口的距離+（k-1）圈數(shù)環(huán)長度。其中k>=1，所以k-1>=0圈。所以兩個指針分別從鏈表頭和相遇點(diǎn)出發(fā)，最后一定相遇于環(huán)入口。

  該證明引用自：知乎

代碼

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead;
        ListNode slow = pHead;
        // 快速節(jié)點(diǎn)終止循環(huán)的條件是當(dāng)前指向的節(jié)點(diǎn)為空或者當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)為空
        while (fast != null && fast.next != null) {
            // 每次步進(jìn)兩步
            fast = fast.next.next;
            // 每次步進(jìn)一步
            slow = slow.next;
            // 代表兩節(jié)點(diǎn)第一次相遇
            if (fast == slow) {
                break;
            }
        }
        // 正常退出循環(huán)代表該鏈表無環(huán)，所以返回null
        if (fast == null || fast.next == null) {
            return null;
        }
        // 選擇一個節(jié)點(diǎn)重置到鏈表頭節(jié)點(diǎn)位置
        fast = pHead;
        // 分別重新以步長為一的速度步進(jìn)直到兩個節(jié)點(diǎn)重新相遇，終止循環(huán)
        while (fast != null && fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        // 返回相遇位置的節(jié)點(diǎn)即為環(huán)的入口
        return slow;
    }
}