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é)一下鏈表的操作：鏈表元素插入和刪除；鏈表的單向移動。為實現(xiàn)鏈表元素插入和刪除，可能的方法包括dummy node和pointer-to-pointer；為實現(xiàn)鏈表的單向移動，就不得不提快慢指針的移動方法了，不但可以檢測是否有cycle，還可以找鏈表的中點(diǎn)。總之，快慢指針移動大法，都說好！我只好奇，第一個發(fā)明這個方法的人，是怎么想到這個方法的，又是來解決什么問題的？ 2. 這里簡單介紹一下快慢指針法：如下圖：
-快指針移動步數(shù)：a+b+(b+c)*n （在cyle里面移動n圈，n>=1）-慢指針移動步數(shù)：a+b-快指針移動速度是慢的2倍，所以：2a+2b=a+(n+1)b+nc-所以：a=(n-1)(b+c)+c;因此，相遇后，把快指針放到head,慢指針放在相遇的地方，相同的速度移動，則：快慢相遇的再次相遇的地方一定是cycle開始的地方，即：可以檢查到cycle，以及break the cycle!
新聞熱點(diǎn)
疑難解答
