給定一個(gè)單鏈表，只給出頭指針h：
- 如何判斷是否存在環(huán)？
- 如何知道環(huán)的長(zhǎng)度？
- 如何找出環(huán)的連接點(diǎn)在哪里？
- 帶環(huán)鏈表的長(zhǎng)度是多少？
下面我們來(lái)依次分析上面的問題。
如何判斷是否存在環(huán)
這里我們考慮使用快慢指針的方式?？熘羔?fast 每次移動(dòng)2個(gè)節(jié)點(diǎn)，慢指針 slow 每次移動(dòng)一個(gè)節(jié)點(diǎn)。如果沒有環(huán)，則 fast 指針將碰到 null，如果有環(huán)，則 fast 會(huì)在若干次移動(dòng)后追上 slow。
為什么呢？假定單鏈表的長(zhǎng)度為n，并且該單鏈表是環(huán)狀的，那么第i次迭代時(shí)，p指向元素i mod n，q指向2i mod n。因此當(dāng)i≡2i(mod n)時(shí)，p與q相遇。而i≡2i(mod n) => (2i - i) mod n = 0 => i mod n = 0 => 當(dāng)i=n時(shí)，p與q相遇。
那么當(dāng)p與q起點(diǎn)不同呢？假定第i次迭代時(shí)p指向元素i mod n，q指向k+2i mod n，其中0<k<n。那么i≡(2i+k)(mod n) => (i+k) mod n = 0 => 當(dāng)i=n-k時(shí)，p與q相遇。
如何知道環(huán)的長(zhǎng)度
由上一部分的分析我們可以知道，當(dāng)起點(diǎn)相同時(shí)，i 等于 n 時(shí)兩者會(huì)再次相遇，所以從相遇點(diǎn)開始，快慢指針再次相遇時(shí)經(jīng)過(guò)的步驟數(shù)為環(huán)的長(zhǎng)度。
如何找出環(huán)的連接點(diǎn)在哪里
假設(shè)第一個(gè)在環(huán)里的節(jié)點(diǎn)為節(jié)點(diǎn) k，那么由上面的分析知道，滿節(jié)點(diǎn)到達(dá) k 節(jié)點(diǎn)時(shí)，快節(jié)點(diǎn)已經(jīng)領(lǐng)先了慢節(jié)點(diǎn) k mod n，所以相遇點(diǎn)在 i = n - k 處。這樣，一個(gè)節(jié)點(diǎn)從相遇點(diǎn)開始，一個(gè)節(jié)點(diǎn)從頭結(jié)點(diǎn)開始，以相同的速度行走，最終，經(jīng)過(guò)k步，一個(gè)剛好從到達(dá)n，即回到了起點(diǎn)處，另外一個(gè)到達(dá)了 k，即起點(diǎn)處。
帶環(huán)鏈表的長(zhǎng)度是多少
已經(jīng)知道了環(huán)的長(zhǎng)度和環(huán)的入口，可以計(jì)算出鏈表的長(zhǎng)度。
