題目描述
一個(gè)鏈表中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)般哼。
答案真的神了吴汪，看了好久好久好久才看懂，記錄一下（感覺再遇到還是不會(huì)想到這個(gè)方法蒸眠。漾橙。。）
鏈接：https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4
來(lái)源：爬憧ǎ客網(wǎng)
? 假設(shè)x為環(huán)前面的路程（黑色路程）霜运，a為環(huán)入口到相遇點(diǎn)的路程（藍(lán)色路程，假設(shè)順時(shí)針走）蒋腮， c為環(huán)的長(zhǎng)度（藍(lán)色+橙色路程）
? 當(dāng)快慢指針相遇的時(shí)候：
此時(shí)慢指針走的路程為Sslow =? x + m * c + a
快指針走的路程為Sfast = x + n * c + a
2 Sslow =? Sfast
2 * ( x + m*c + a ) = (x + n *c + a)
從而可以推導(dǎo)出：
x = (n? - 2 * m )*c - a
= (n - 2 *m -1 )*c + c - a
即環(huán)前面的路程 =? 數(shù)個(gè)環(huán)的長(zhǎng)度（為可能為0） + c - a
什么是c - a淘捡？這是相遇點(diǎn)后，環(huán)后面部分的路程池摧。（橙色路程）
所以焦除，我們可以讓一個(gè)指針從起點(diǎn)A開始走，讓一個(gè)指針從相遇點(diǎn)B開始繼續(xù)往后走作彤，
2個(gè)指針?biāo)俣纫粯颖炱牵敲矗?dāng)從原點(diǎn)的指針走到環(huán)入口點(diǎn)的時(shí)候（此時(shí)剛好走了x）
從相遇點(diǎn)開始走的那個(gè)指針也一定剛好到達(dá)環(huán)入口點(diǎn)竭讳。
所以2者會(huì)相遇创葡，且恰好相遇在環(huán)的入口點(diǎn)。
? 最后代咸，判斷是否有環(huán)蹈丸，且找環(huán)的算法復(fù)雜度為：
? 時(shí)間復(fù)雜度：O(n)
? 空間復(fù)雜度：O(1)
