Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?
s思路： 1. 經(jīng)典的題目！在這里突然想總結(jié)一下鏈表的操作：鏈表元素插入和刪除；鏈表的單向移動(dòng)。為實(shí)現(xiàn)鏈表元素插入和刪除，可能的方法包括dummy node和pointer-to-pointer；為實(shí)現(xiàn)鏈表的單向移動(dòng)，就不得不提快慢指針的移動(dòng)方法了，不但可以檢測(cè)是否有cycle，還可以找鏈表的中點(diǎn)。總之，快慢指針移動(dòng)大法，都說(shuō)好！我只好奇，第一個(gè)發(fā)明這個(gè)方法的人，是怎么想到這個(gè)方法的，又是來(lái)解決什么問(wèn)題的？ 2. 這里簡(jiǎn)單介紹一下快慢指針?lè)ǎ喝缦聢D：
-快指針移動(dòng)步數(shù)：a+b+(b+c)*n （在cyle里面移動(dòng)n圈，n>=1）-慢指針移動(dòng)步數(shù)：a+b-快指針移動(dòng)速度是慢的2倍，所以：2a+2b=a+(n+1)b+nc-所以：a=(n-1)(b+c)+c;因此，相遇后，把快指針?lè)诺絟ead,慢指針?lè)旁谙嘤龅牡胤剑嗤乃俣纫苿?dòng)，則：快慢相遇的再次相遇的地方一定是cycle開(kāi)始的地方，即：可以檢查到cycle，以及break the cycle!
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
