這道題是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; }這道題是鏈表中比較有意思的題目,基於這個方法,我們不僅可以判斷鏈表中有沒有cycle,還可以確定cycle的位置,有興趣的朋友可以看看Linked List Cycle II。