這題本來(lái)以為很簡(jiǎn)單缝裤，看了題解發(fā)現(xiàn)各種推倒嬉挡，被嚇到了荞胡。郁妈。
找了一個(gè)簡(jiǎn)單的容易懂的題解：
以下講解引用自:http://www.reibang.com/p/ce7f035daf74
圖中枉证，
X是鏈表的起點(diǎn)鼓寺。
Y是環(huán)的起點(diǎn)配并。
Z是fast和slow首次相遇的地方（二者同時(shí)從X出發(fā)光酣，slow每次移動(dòng)一步，fast每次移動(dòng)兩步）揍障。
a, b, c分別表示XY（藍(lán)色）, YZ（紅色）, ZY（綠色）的長(zhǎng)度目养。
當(dāng)fast和slow在Z點(diǎn)首次相遇時(shí)：
fast移動(dòng)的距離是：a + b + c + b
slow移動(dòng)的距離是：a + b
因?yàn)閒ast的移動(dòng)速度是slow的兩倍，所以：
(a + b + c + b) == 2 * (a + b)
由此可以推出：
a == c
我們需要用上面的推論來(lái)尋找環(huán)的起點(diǎn)（Y）毒嫡。
當(dāng)fast和slow首次相遇時(shí)癌蚁，我們就到了Z點(diǎn)。
由于a == c兜畸，也就是X到Y(jié) 與 Z到Y(jié)的距離相等努释。
因此，如果我們讓指針p和q分別從X和Z出發(fā)咬摇，并且每次都移動(dòng)一步伐蒂，當(dāng)它們相遇時(shí)，恰好就是環(huán)的起點(diǎn)Y肛鹏。
我說(shuō)這個(gè)推倒簡(jiǎn)單逸邦，是因?yàn)檫@個(gè)推導(dǎo)有一個(gè)問(wèn)題，就是有可能runner并不是只在一圈內(nèi)就遇到了walker在扰。但是無(wú)傷大雅昭雌，無(wú)論經(jīng)過(guò)幾圈相遇，a=c仍然是可行的健田，所以這種相遇后分別走一步直到相遇的方法是可行的烛卧。就不要考慮太復(fù)雜的數(shù)學(xué)推導(dǎo)啦。
下面是我按上面思路寫(xiě)的Java代碼：
public ListNode detectCycle(ListNode head) {
if (head == null) return null;
ListNode walker = head;
ListNode runner = head;
ListNode meetPoint = null;
while (runner.next != null && runner.next.next != null) {
walker = walker.next;
runner = runner.next.next;
if (walker == runner) {
meetPoint = walker;
break;
}
}
if (meetPoint == null) return null;
//注意這里的while條件
while (head != meetPoint) {
head = head.next;
meetPoint = meetPoint.next;
}
return head;
}
