柚子快報邀請碼778899分享：c語言 【數(shù)據(jù)結(jié)構(gòu)】鏈表專題3

http://yzkb.51969.com/

前言

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

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

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

若有問題 評論區(qū)見?

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

目錄

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

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

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

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

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

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

?我們來畫圖分析一下

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

代碼如下

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

為什么一定會相遇，有沒有可能會錯過，永遠(yuǎn)追不上？

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

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

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錯過了，需要新的一輪追擊，此刻他們之間的距離就變成了C-1，繼續(xù)追擊，我們根據(jù)第一輪追擊可以得知，C-1是偶數(shù)的話代表第二輪追上了，C-1還是奇數(shù)的話，又錯了一位，距離又變成了C-1，C-1既然是奇數(shù)，那就代表永遠(yuǎn)追不上了

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

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

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

那么slow剛進(jìn)環(huán)時，slow走過的距離是L，此刻我們假設(shè)fast走了x圈，那fast走過的距離就是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ù)時，C必須是奇數(shù)，才能使等式成立，N是偶數(shù)時，C必須也是偶數(shù)，才能使等式成立。

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

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

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

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

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

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

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

代碼如下

可是為什么那？

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

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

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

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

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

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

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

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

我們畫圖看一下

這一步代碼如下

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

第二步代碼如下

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

代碼如下

這道題整體代碼如下

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

結(jié)束語?

鏈表有關(guān)算法題也就總結(jié)完了，從鏈表專題1到3都是特別經(jīng)典的算法題，我們一定要反復(fù)練習(xí)掌握，OK，感謝觀看?。?！

柚子快報邀請碼778899分享：c語言 【數(shù)據(jù)結(jié)構(gòu)】鏈表專題3

http://yzkb.51969.com/

好文推薦