如何判斷一個單鏈表是有環(huán)的？給定一個單鏈表，嘗試判斷單鏈表中是否有環(huán)。答：該算法的思想是設置兩個指針P和Q，其中P一次向前移動一步，Q一次向前移動兩步。如果單鏈表中有一個環(huán)，那么p和Q相遇；否則，Q將

如何判斷一個單鏈表是有環(huán)的？

給定一個單鏈表，嘗試判斷單鏈表中是否有環(huán)。答：該算法的思想是設置兩個指針P和Q，其中P一次向前移動一步，Q一次向前移動兩步。如果單鏈表中有一個環(huán)，那么p和Q相遇；否則，Q將首先遇到null。R假設單鏈表的長度為n，單鏈表是循環(huán)的，那么在第i次迭代中，P指向元素i mod n，Q指向元素2I mod n，所以當i≡2I（mod n）時，P和Q滿足。當I=n，P和Q滿足時，I≡2I（MOD n）=>（2I-I）MOD n=0=> I MOD n=0=>。這里有一個簡單的理解，就是P和Q同時在操場上跑，Q跑的速度是P的兩倍，當他們兩人同時出發(fā)時，P跑一圈就到了起點，Q跑兩圈就到了起點。如果P的起點和Q的起點不同呢？假設在第I次迭代時P指向元素I mod N，Q指向k2i mod N，其中0