?

目錄

1.環(huán)形鏈表Ⅰ

?編輯

思路 ：

思路拓展?

問題一：

問題二：

總結(jié)：?

問題三：

證明總結(jié)第三點(diǎn)?

?總結(jié)：

2. 環(huán)形鏈表Ⅱ

思路一

思路二?

3.相交鏈表?

?思路：

---

?

1.環(huán)形鏈表Ⅰ

141. 環(huán)形鏈表 - 力扣（LeetCode）

給你一個(gè)鏈表的頭節(jié)點(diǎn)?head?，判斷鏈表中是否有環(huán)。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤?next?指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù)?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos?不作為參數(shù)進(jìn)行傳遞?。僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。

如果鏈表中存在環(huán)?，則返回?true?。 否則，返回?false?。

思路 ：

? ? ? ? 我們考慮環(huán)狀時(shí)，如果是簡單的循環(huán)next來判定，只會(huì)進(jìn)入死循環(huán)；

需要引入新思維，判斷是否帶環(huán)，可以想象操場(chǎng)追趕問題，兩個(gè)人在操場(chǎng)跑；讓一個(gè)人先進(jìn)場(chǎng)跑，再讓另外一名選手進(jìn)場(chǎng)，如果環(huán)足夠大，如何讓后入場(chǎng)的選手追趕上前面的；答案是，后來者加快速度。

? ? ? ? 而在這道題中，我們用快慢指針概念，一個(gè)指針走兩步，一個(gè)走一步，進(jìn)入環(huán)后，快指針一定會(huì)和慢指針相遇

為什么一定會(huì)相遇呢？

距離為N，每次快指針走兩步，慢指針走一步相當(dāng)于距離每次減少1；

如此距離縮短，肯定會(huì)相遇，而當(dāng)快慢指針相遇的時(shí)候，就是證明該鏈表帶環(huán)；

而如果不帶環(huán)，快指針將鏈表走完后，表明退出了循環(huán)即可；?

?

?

bool hasCycle(struct ListNode *head) {//快慢指針struct ListNode* slow = head;struct ListNode* fast = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(fast == slow){return true;}}return false;
}

思路拓展?

上面說到，距離縮小1一定會(huì)追上，那如果距離一次縮小2呢，是不是更快的會(huì)相遇呢

如果一次距離縮小n，是不是更快呢；如此延申，我們可以發(fā)現(xiàn)有三個(gè)拓展

?1. slow一次走一步，fast一次走兩步，一定會(huì)相遇嗎

2.slow一次走一步，fast一次走三步，一定會(huì)相遇嗎

3.slow一次走n步，fast一次走m步，一定會(huì)相遇嗎? ? ? ? （m>n>1）

問題一：

?距離縮小為1的話，一定會(huì)遇上，我們上面證明了

問題二：

?當(dāng)slow進(jìn)環(huán)時(shí)，fast和它的距離為N，一次減少2。分為兩種情況

1.當(dāng)N是偶數(shù)時(shí)：

2.當(dāng)N是奇數(shù)時(shí)：

所以，我們可以發(fā)現(xiàn)，當(dāng)N是偶數(shù)時(shí)，依然可以追上

當(dāng)N是奇數(shù)是，得到下一輪：

這時(shí)候要看 C-1是奇偶數(shù)

如果c-1是偶數(shù)：在下一輪就會(huì)追上，

如果c-是奇數(shù)：則會(huì)開始無限循環(huán)下去，一直追擊不上；

總結(jié)：?

1.如果N是偶數(shù)，第一輪內(nèi)就會(huì)追上；

2.如果N是奇數(shù)，C是奇數(shù)，第一輪會(huì)錯(cuò)過，下一輪會(huì)追擊（C是奇數(shù)，C-1就會(huì)是偶數(shù)）；

3.如果N是奇數(shù)，C是偶數(shù)，就永遠(yuǎn)追不上；

問題三：

?這個(gè)類似問題二，每次距離縮小是m-n(>=1);

如果N%(m-n) == 0? 說明一圈就可以追上；

如果是-1，則是C-1，-2就是C-2；

如果這個(gè)數(shù)是m-n的倍數(shù)，如果不是倍數(shù)，則可能存在死循環(huán)? ? ? ??

證明總結(jié)第三點(diǎn)?

寫到這里時(shí)，問題二的?總結(jié)第三點(diǎn)，是否真的成立呢？

3.如果N是奇數(shù)，C是偶數(shù)，就永遠(yuǎn)追不上；

?此刻，slow走了L的路程，fast走了 L + nC - N；?

在這時(shí)，可以推論出公式?

?

?推論出來的這個(gè)公式：

2L：一定是偶數(shù)，

n*C:總結(jié)第三點(diǎn)假設(shè)這里是偶數(shù)；

N：如果要滿足此公式，N就不可能會(huì)奇數(shù)，

所以，?3.如果N是奇數(shù)，C是偶數(shù)，就永遠(yuǎn)追不上；

這句話的條件不成立

?總結(jié)：

1.如果N是偶數(shù)，第一輪內(nèi)就會(huì)追上；

2.如果N是奇數(shù)，C是奇數(shù)，第一輪會(huì)錯(cuò)過，下一輪會(huì)追擊（C是奇數(shù)，C-1就會(huì)是偶數(shù)）；

只存在這兩種

bool hasCycle(struct ListNode *head) {//快慢指針struct ListNode* slow = head;struct ListNode* fast = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(fast == slow){return true;}}return false;
}

?

在這種情況下，該情況其實(shí)還可以推論出另一個(gè)公式結(jié)論?。這就是第二題

2. 環(huán)形鏈表Ⅱ

?142. 環(huán)形鏈表 II - 力扣（LeetCode）

給定一個(gè)鏈表的頭節(jié)點(diǎn) ?head?，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。?如果鏈表無環(huán)，則返回?null。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤?next?指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù)?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果?pos?是?-1，則在該鏈表中沒有環(huán)。注意：pos?不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。

不允許修改?鏈表。

思路一

?我們依舊用上一道題的畫圖思路來解決，

第一步先判斷是否存在環(huán)，

第二部找到入口點(diǎn)；

?

用快慢指針方法，slow走一步，fast走兩步

?

struct ListNode *detectCycle(struct ListNode *head) {//快慢指針struct ListNode* slow = head;struct ListNode* fast = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(fast == slow) //相遇了{(lán)struct ListNode* meet = slow;while(head != meet)   //起點(diǎn)和相遇點(diǎn){head = head->next;meet = meet->next;}//找到入口點(diǎn)了return meet;}}return false;
}

思路二?

?這道題還有另外一種解法，就是在相遇點(diǎn)meet這里，將下一個(gè)節(jié)設(shè)為newnode，再將meet->next置NULL，這樣就將帶環(huán)鏈表問題轉(zhuǎn)換成 相交鏈表問題

而這種解法自然有相交鏈表的題；

但是這種解法比較復(fù)雜，建議用思路一的

3.相交鏈表?

160. 相交鏈表 - 力扣（LeetCode）

給你兩個(gè)單鏈表的頭節(jié)點(diǎn)?headA?和?headB?，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表不存在相交節(jié)點(diǎn)，返回?null?。

題目數(shù)據(jù)?保證?整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。

注意，函數(shù)返回結(jié)果后，鏈表必須?保持其原始結(jié)構(gòu)?。

?

?思路：

題目兩種情況，存在相交和不相交，

相交還有前后長短問題；

1.先判斷是否有相交點(diǎn)；如果相交，尾節(jié)點(diǎn)一定相同；

2.計(jì)算兩條鏈表的長度，讓長鏈表先走差距步，這樣可以讓兩條鏈表處于相同head；

3.再讓兩條鏈接一起走，直到遇到相同點(diǎn)；

返回相遇點(diǎn)或者是結(jié)束鏈表遍歷返回NULL；

?

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA = headA,*curB = headB;//計(jì)算兩條鏈表長度int lenA = 0;int lenB = 0;while(curA){lenA++;curA = curA->next;}while(curB){lenB++;curB = curB->next;}//算出長度差int n = abs(lenA-lenB);//假設(shè)lenA 長于lenBstruct ListNode* longlist = headA,*shortlist = headB;if(lenB>lenA) //假設(shè)不成立，交換{longlist = headB;shortlist = headA;}//長的先走差值while(n--){longlist = longlist->next;}//判斷是否相等while(longlist != shortlist){longlist = longlist->next;shortlist = shortlist->next; }//到這里要么相等，要么鏈表不相交，已經(jīng)走完了是NULLreturn longlist;
}

? ? ???