題目
Description
Given a linked list, return the node where the cycle begins.
If there is no cycle, return null.
Example
Given -21->10->4->5, tail connects to node index 1荠瘪，return 10
Challenge
Follow up:
Can you solve it without using extra space?
分析
問題分解
basic problem
單鏈表中確定有無環(huán)
暴力方法是使用hash表統(tǒng)計(jì)節(jié)點(diǎn)的出現(xiàn)次數(shù)请契，O(n)的space冰肴。不過一般是希望以O(shè)(1)的space解決：
- 設(shè)置一個快指針fast和一個慢指針slow绒净，它們同時從鏈表頭開始往后遍歷褪迟，快指針每次移動兩個位置，慢指針每次移動一個位置
- 如果在快指針訪問到null（即無環(huán)）之前虽填，快指針和慢指針相遇蔬咬，就說明有環(huán)
follow up
確定環(huán)入口入口的位置
和basic problem一樣，可以用hash表解決谚中。而follow up的目的仍然是希望O(1)的space解決：
- 重復(fù)上述判定有環(huán)無環(huán)的過程
- 用一個新指針指向head渴杆，與slow指針同時一次移動一個位置
- 當(dāng)head與slow相遇時，指針?biāo)傅墓?jié)點(diǎn)即入口節(jié)點(diǎn)
證明
相遇一定有環(huán)
反證法：
如果無環(huán)，則fast一定比slow先到達(dá)null，不會相遇贡必。因此，如果fast與slow相遇比搭，則一定有環(huán)。
得證南誊。
第一次相遇一定發(fā)生在slow第一次入環(huán)的過程中
該結(jié)論是下一步推導(dǎo)的前提身诺。
設(shè)鏈表頭節(jié)點(diǎn)為head蜜托，環(huán)入口節(jié)點(diǎn)為entrance，head到entrance共有n個節(jié)點(diǎn)霉赡，環(huán)上共有m個節(jié)點(diǎn)橄务。顯然，fast和slow相遇的節(jié)點(diǎn)一定在環(huán)中同廉，設(shè)從entrance到這個節(jié)點(diǎn)共k個節(jié)點(diǎn)仪糖。
PS：代碼實(shí)現(xiàn)時柑司，需要關(guān)注m迫肖、n、k等計(jì)算時是否包含head攒驰、entrance等蟆湖，但證明時無需關(guān)心，僅僅是加減一個常數(shù)項(xiàng)的事情玻粪。
fast的速度是slow的兩倍隅津。則，fast第一次到entrance時劲室，slow到達(dá)鏈表中部節(jié)點(diǎn)mid伦仍，設(shè)head到mid共有s個節(jié)點(diǎn)，則此時很洋，slow走了s個節(jié)點(diǎn)充蓝，fast走了2s個節(jié)點(diǎn)。我們讓slow再走s個節(jié)點(diǎn)喉磁，fast再走2s個節(jié)點(diǎn)谓苟，分情況討論：
如果entrance等于head
此情況下環(huán)最長。經(jīng)過s個節(jié)點(diǎn)协怒，slow恰好第一次到達(dá)entrance涝焙；經(jīng)過2s個節(jié)點(diǎn)，fast恰好第二次到達(dá)entrance孕暇。在此過程中仑撞，slow有且僅有一次從mid走到entrance，fast有且僅有一次從head經(jīng)過mid走到entrance妖滔，從而隧哮，fast與slow必然有且僅有一次在mid于entrance之間相遇，這是二者第一次相遇铛楣。由于相遇點(diǎn)一定在環(huán)中近迁，因此第一次相遇一定發(fā)生在slow第一次入環(huán)的過程中。
如果entrance不等于head
此情況下簸州，環(huán)均比第一種情況短鉴竭。重復(fù)上述過程歧譬，slow仍然有且僅有一次從mid走到entrance，但fast卻由于環(huán)的縮短搏存，可能不止一次與slow相遇并走到entrance瑰步。我們只關(guān)注第一次相遇，顯然璧眠，第一次相遇仍然發(fā)生在slow第一次入環(huán)的過程中缩焦。
得證。
如何尋找入口節(jié)點(diǎn)
我們現(xiàn)在知道责静，“第一次相遇一定發(fā)生在slow第一次入環(huán)的過程中”袁滥，那么此時slow共走了n+k個節(jié)點(diǎn)，fast共移動了n+k + x*m個節(jié)點(diǎn)灾螃。fast速度是slow的2倍题翻，則有2*(n+k) = n+k + x*m，其中x表示fast已經(jīng)在環(huán)中走的圈數(shù)腰鬼。由此可得嵌赠，n+k = x*m，從而n = (x-1)*m + m-k(x>=1, m>=k)熄赡。
在有環(huán)鏈表中姜挺，我們只能基于移動和相遇進(jìn)行判斷。basic problem中彼硫，我們希望通過相遇判斷是否有環(huán)炊豪，follow up中，可以試著用相遇找到entrance節(jié)點(diǎn)乌助。
觀察式n = (x-1)*m + m-k：
-
n為head到entrance的節(jié)點(diǎn)數(shù) -
m為環(huán)的長度 -
m-k為從fast溜在、slow的相遇點(diǎn)到entrance的節(jié)點(diǎn)數(shù)
如果讓slow繼續(xù)走m-k個節(jié)點(diǎn)，此時slow將恰好位于entrance他托；再循環(huán)y = x-1圈掖肋，仍然處于entrance。增加一個新的指針p = head赏参，則可以這樣理解上式：使p和slow同時開始移動（slow從剛才的相遇點(diǎn)開始）志笼，都一次移動一個位置，則當(dāng)p第一次經(jīng)過n個節(jié)點(diǎn)走到entrance時把篓，slow恰好先經(jīng)過了m-k個節(jié)點(diǎn)纫溃，再走了整y圈回到entrance。
此時韧掩，p與slow相遇紊浩，相遇點(diǎn)即為entrance。
代碼
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The first node of linked list.
* @return: The node where the cycle begins.
* if there is no cycle, return null
*/
public ListNode detectCycle(ListNode head) {
// write your code here
if (head == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast == null || fast.next == null) {
return null;
}
ListNode p = head;
while (p != slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
本文鏈接：【刷題】Linked List Cycle II
作者：猴子007
出處：https://monkeysayhi.github.io
本文基于 知識共享署名-相同方式共享 4.0 國際許可協(xié)議發(fā)布，歡迎轉(zhuǎn)載坊谁，演繹或用于商業(yè)目的费彼，但是必須保留本文的署名及鏈接。
