柚子快報(bào)邀請(qǐng)碼778899分享：c語(yǔ)言【數(shù)據(jù)結(jié)構(gòu)】鏈表專(zhuān)題3

TweetShop跨境推特購(gòu)綜合2025-05-05440

http://yzkb.51969.com/

前言

本篇博客我們繼續(xù)來(lái)討論鏈表專(zhuān)題，今天的鏈表算法題是經(jīng)典中的經(jīng)典

? 個(gè)人主頁(yè)：小張同學(xué)zkf

? 文章專(zhuān)欄：數(shù)據(jù)結(jié)構(gòu)

若有問(wèn)題評(píng)論區(qū)見(jiàn)?

?歡迎大家點(diǎn)贊?收藏?文章

1.判斷鏈表是否有環(huán)

2.返回入環(huán)的第一個(gè)節(jié)點(diǎn)

3.隨機(jī)鏈表的復(fù)制

1.判斷鏈表是否有環(huán)

這道題鏈表尾指針很有可能指向鏈表中任何一個(gè)節(jié)點(diǎn)，所以是帶環(huán)的意思，當(dāng)然尾指針很有可能指向他自己

所以我們分析一下，該怎么判斷帶有環(huán)，有些人直接說(shuō)我就判斷是否和我原來(lái)的值相等，相等的話(huà)就是代表有環(huán)，但這種情況不能確保一定有環(huán)，因?yàn)榧词刮覜](méi)進(jìn)環(huán)也有可能值相等，所以這個(gè)行不通，所以我們要判斷的話(huà)還得需要快慢指針，若快指針追上慢指針代表這鏈表有環(huán)，為什么快指針追上慢指針就會(huì)帶有環(huán)那？

?我們來(lái)畫(huà)圖分析一下

slow和fast最初都在頭結(jié)點(diǎn)，?我們讓fast一次走兩步，slow一次走一步，假如沒(méi)換那么fast或fast->next就會(huì)指向空，假如有環(huán)，那么fast先進(jìn)環(huán)，slow后進(jìn)環(huán)，若fast追上slow就證明了這個(gè)鏈表就帶有環(huán)

代碼如下

這道題曾經(jīng)被一個(gè)面試官提出新的問(wèn)題

為什么一定會(huì)相遇，有沒(méi)有可能會(huì)錯(cuò)過(guò)，永遠(yuǎn)追不上？

我們先來(lái)看第一個(gè)問(wèn)題，我們假設(shè)slow進(jìn)環(huán)后與fast距離為N, 環(huán)的長(zhǎng)度是C

那么fast追擊slow的過(guò)程距離變化如下：

N為偶數(shù)? ? ? ? ? ? ? ? ?N為奇數(shù)?

N? ? ? ? ? ? ? ? ? ? ? ? ? ? N

N-2? ? ? ? ? ? ? ? ? ? ? ? ?N-2

N-4? ? ? ? ? ? ? ? ? ? ? ? ?N-4

……? ? ? ? ? ? ? ? ? ? ? ?……

4? ? ? ? ? ? ? ? ? ? ? ? ? ? ?3

2? ? ? ? ? ? ? ? ? ? ? ? ? ? 1

0? ? ? ? ? ? ? ? ? ? ? ? ? ? ?-1

可以看出N若為偶數(shù)追上了，若N為奇數(shù)，則代表fast錯(cuò)過(guò)了，需要新的一輪追擊，此刻他們之間的距離就變成了C-1，繼續(xù)追擊，我們根據(jù)第一輪追擊可以得知，C-1是偶數(shù)的話(huà)代表第二輪追上了，C-1還是奇數(shù)的話(huà)，又錯(cuò)了一位，距離又變成了C-1，C-1既然是奇數(shù)，那就代表永遠(yuǎn)追不上了

所以追不上的條件前提是，第二輪的C-1是奇數(shù)，第一輪的N是奇數(shù)，但我們想想這兩個(gè)條件會(huì)不會(huì)同時(shí)存在

這里我們就需要用到數(shù)學(xué)列等式的思維來(lái)判斷兩個(gè)條件是否可以同時(shí)存在

我們假設(shè)進(jìn)環(huán)之前的距離是L

那么slow剛進(jìn)環(huán)時(shí)，slow走過(guò)的距離是L，此刻我們假設(shè)fast走了x圈，那fast走過(guò)的距離就是L+x*C+C-N

fast的距離是slow的三倍

那么就有了等式

3L=L+x*C+C-N

換算為：2*L=（x+1)*C-N

偶數(shù)=（x+1)*偶數(shù)-奇數(shù)

我們根據(jù)數(shù)學(xué)運(yùn)算法則中 ,N是奇數(shù)時(shí)，C必須是奇數(shù)，才能使等式成立，N是偶數(shù)時(shí)，C必須也是偶數(shù)，才能使等式成立。

所以，當(dāng)N是奇數(shù)時(shí)，C為奇數(shù)，C-1為偶數(shù)，所以C-1不可能為奇數(shù)，所以不可能永遠(yuǎn)追不上，肯定相遇。? ? ? ? ? ? ? ? ? ? ? ?

結(jié)論：一定能追上

N是偶數(shù)第一輪就追上了

N是奇數(shù)第一輪追不上，第二輪就追上了

2.返回入環(huán)的第一個(gè)節(jié)點(diǎn)

上面那道題是判斷是否有環(huán)，這道題就是若有環(huán)，返回環(huán)的第一個(gè)節(jié)點(diǎn)，所以我們還是需要用到快慢指針，我們畫(huà)圖表示

如圖，這里其實(shí)有個(gè)非常巧妙的方法，我們讓慢指針一次走一步，快指針一次走兩步，直到環(huán)里相遇，再創(chuàng)建兩個(gè)指針，一個(gè)從頭開(kāi)始走，另一個(gè)從快慢指針相遇的地方開(kāi)始走，倆指針一次走一步，這倆指針若相遇，則相遇的點(diǎn)必定是進(jìn)環(huán)的首節(jié)點(diǎn)

代碼如下

可是為什么那？

我們還是用數(shù)學(xué)的方法來(lái)證明一下?

我們假設(shè)，環(huán)之前的距離是L，環(huán)的長(zhǎng)度為C，相遇點(diǎn)與入環(huán)點(diǎn)的距離為N，在慢指針進(jìn)入環(huán)點(diǎn)時(shí)，快指針走了x圈

那么相遇時(shí)，slow走的距離是L+N

fast走的距離是L+x*C+N

fast走的路程是slow兩倍

那么就有了等式

2*（L+N）=L+x*C+N

最后換算成L=（x-1）*C+C-N

假如x=1，那么L=C-N，正好是相遇點(diǎn)到入環(huán)首節(jié)點(diǎn)的距離與入環(huán)之前的距離相等，那么此時(shí)在頭結(jié)點(diǎn)與相遇節(jié)點(diǎn)創(chuàng)建倆指針同時(shí)走，正好相遇在入環(huán)首節(jié)點(diǎn)，證實(shí)了我們上面的代碼想法，但有人會(huì)想，你這里假設(shè)為1呀，我讓它不為一，不唯一的話(huà)，相當(dāng)于在相遇節(jié)點(diǎn)的指針多走了幾圈C，最后還是在入環(huán)首節(jié)點(diǎn)相遇。

3.隨機(jī)鏈表的復(fù)制

這道題鏈表每個(gè)節(jié)點(diǎn)里多了個(gè)指針指向隨機(jī)節(jié)點(diǎn)，也有可能指向空，然后我們要深拷貝一份（深拷貝意思就是把指針指向?qū)?yīng)的值對(duì)應(yīng)關(guān)系也要在新拷貝的鏈表中實(shí)現(xiàn)），有人說(shuō)我直接遍歷然后拷貝不就行了，硬拷貝是可以的，但是有個(gè)問(wèn)題，隨機(jī)指針（random）指向的值如何在新鏈表中實(shí)現(xiàn)，有人說(shuō)我在新鏈表里繼續(xù)找就行呀，但是我們仔細(xì)想一下，我們鏈表里值有可能有時(shí)相等，所以如果你先拷貝過(guò)去，然后再去找對(duì)應(yīng)的值，可能找到的值不是原鏈表對(duì)應(yīng)的值，而是值相等的那個(gè)位置的節(jié)點(diǎn)。

比如就會(huì)出現(xiàn)圖上這個(gè)情況，11找的就不是原來(lái)第四位的7，而是第一位的7，這就沒(méi)拷貝成功。

所以這道題這種做法是不行的

我們先想一下，這道題我們要是先靠拷貝一下，然后插在原節(jié)點(diǎn)的后面其拷貝的節(jié)點(diǎn)就與源節(jié)點(diǎn)有了對(duì)應(yīng)的關(guān)聯(lián)關(guān)系

我們畫(huà)圖看一下

這一步代碼如下

第二步控制random，拷貝完了，那拷貝那一份鏈表里的random怎么找那，其實(shí)很簡(jiǎn)單，拷貝的random是不是就是原值的random的next（這一點(diǎn)仔細(xì)想想，這一點(diǎn)想明白，這道題就沒(méi)什么難點(diǎn)了）

第二步代碼如下

第三步尾插新鏈表，將拷貝在原鏈表的節(jié)點(diǎn)尾插新鏈表，并返回新鏈表的頭結(jié)點(diǎn)

代碼如下

這道題整體代碼如下

相當(dāng)于三個(gè)while嘛，一個(gè)while循環(huán)一步

結(jié)束語(yǔ)?