Linked List Cycle -- LeetCode

 
這道題是cc150裡面的題目，算是鏈表裡面比較經典的題目。
我們先講一下比較直接容易想到的方法，就是用一個hashset，然後把掃過的結點放入hashset中，如果出現重復則返回true。想法比較簡單，也很好實現，這裡就不放代碼了，有興趣的朋友可以寫寫。
下面我們來考慮如何不用額外空間來判斷是否有cycle，用到的方法很典型，就是那種walker-runner的方法，基本想法就是維護兩個指針，一個走的快，一個走得慢，當一個走到鏈表尾或者兩個相見的時候，能得到某個想要的結點，比如相遇點，中點等等。
介紹完方法，剩下的主要就是數學了，假設兩個指針walker和runner，walker一倍速移動，runner兩倍速移動。有一個鏈表，假設他在cycle開始前有a個結點，cycle長度是c，而我們相遇的點在cycle開始後b個結點。那麼想要兩個指針相遇，意味著要滿足以下條件：(1) a+b+mc=s; (2) a+b+nc=2s; 其中s是指針走過的步數，m和n是兩個常數。這裡面還有一個隱含的條件，就是s必須大於等於a，否則還沒走到cycle裡面，兩個指針不可能相遇。假設k是最小的整數使得a<=kc，也就是說(3) a<=kc<=a+c。接下來我們取m=0, n=kc，用(2)-(1)可以得到s=kc以及a+b=kc。由此我們可以知道，只要取b=kc-a(由(3)可以知道b不會超過c)，那麼(1)和(2)便可以同時滿足，使得兩個指針相遇在離cycle起始點b的結點上。
因為s=kc<=a+c=n，其中n是鏈表的長度，所以走過的步數小於等於n，時間復雜度是O(n)。並且不需要額外空間，空間復雜度O(1)。代碼如下：

public boolean hasCycle(ListNode head) {
    if(head == null)
        return false;
    ListNode walker = head;
    ListNode runner = head;
    while(runner!=null && runner.next!=null)
    {
        walker = walker.next;
        runner = runner.next.next;
        if(walker == runner)
            return true;
    }
    return false;
}