前言

本文章一部分內(nèi)容參考于《代碼隨想錄》----如有侵權(quán)請聯(lián)系作者刪除即可，撰寫本文章主要目的在于記錄自己學(xué)習(xí)體會并分享給大家，全篇并不僅僅是復(fù)制粘貼，更多的是加入了自己的思考，希望讀完此篇文章能真正幫助到您?。?！

算法題（LeetCode刷題142環(huán)形鏈表II）—（保姆級別講解）

力扣題目鏈接

分析題目：

1. 其實(shí)本題目中主要解決兩個問題，分別是：

1. 判斷鏈表是否有環(huán)
2. 如果有環(huán)，如何找到這個環(huán)的入口。

算法思想

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

可以使用快慢指針法，分別定義 fast 和 slow 指針，從頭結(jié)點(diǎn)出發(fā)，fast指針每次移動兩個節(jié)點(diǎn)，slow指針每次移動一個節(jié)點(diǎn)，如果 fast 和 slow指針在途中相遇 ，說明這個鏈表有環(huán)。
為什么fast 走兩個節(jié)點(diǎn)，slow走一個節(jié)點(diǎn)，有環(huán)的話，一定會在環(huán)內(nèi)相遇呢，而不是永遠(yuǎn)的錯開呢
首先第一點(diǎn)：fast指針一定先進(jìn)入環(huán)中，如果fast指針和slow指針相遇的話，一定是在環(huán)中相遇，這是毋庸置疑的。
那么來看一下，為什么fast指針和slow指針一定會相遇呢？
可以畫一個環(huán)，然后讓 fast指針在任意一個節(jié)點(diǎn)開始追趕slow指針。
會發(fā)現(xiàn)最終都是這種情況， 如下圖：

fast和slow各自再走一步， fast和slow就相遇了

這是因?yàn)?code>fast是走兩步，slow是走一步，其實(shí)相對于slow來說，fast是一個節(jié)點(diǎn)一個節(jié)點(diǎn)的靠近slow的，所以fast一定可以和slow重合。

2. 如果有環(huán)，如何找到這個環(huán)的入口

此時已經(jīng)可以判斷鏈表是否有環(huán)了，那么接下來要找這個環(huán)的入口了。

假設(shè)從頭結(jié)點(diǎn)到環(huán)形入口節(jié)點(diǎn) 的節(jié)點(diǎn)數(shù)為x。 環(huán)形入口節(jié)點(diǎn)到 fast指針與slow指針相遇節(jié)點(diǎn) 節(jié)點(diǎn)數(shù)為y。 從相遇節(jié)點(diǎn) 再到環(huán)形入口節(jié)點(diǎn)節(jié)點(diǎn)數(shù)為 z。 如圖所示：

那么相遇時： slow指針走過的節(jié)點(diǎn)數(shù)為: x + y， fast指針走過的節(jié)點(diǎn)數(shù)：x + y + n (y + z)，n為fast指針在環(huán)內(nèi)走了n圈才遇到slow指針， （y+z）為 一圈內(nèi)節(jié)點(diǎn)的個數(shù)。

因?yàn)?code>fast指針是一步走兩個節(jié)點(diǎn)，slow指針一步走一個節(jié)點(diǎn)， 所以 fast指針走過的節(jié)點(diǎn)數(shù) = slow指針走過的節(jié)點(diǎn)數(shù) * 2：

(x + y) * 2 = x + y + n (y + z)

兩邊消掉一個（x+y）: x + y = n (y + z)

因?yàn)橐噎h(huán)形的入口，那么要求的是x，因?yàn)?code>x表示 頭結(jié)點(diǎn)到 環(huán)形入口節(jié)點(diǎn)的的距離。

所以要求x ，將x單獨(dú)放在左面：x = n (y + z) - y ,

再從n(y+z)中提出一個 （y+z）來，整理公式之后為如下公式：x = (n - 1) (y + z) + z 注意這里n一定是大于等于1的，因?yàn)?fast指針至少要多走一圈才能相遇slow指針。

這個公式說明什么呢？

先拿n為1的情況來舉例，意味著fast指針在環(huán)形里轉(zhuǎn)了一圈之后，就遇到了 slow指針了。

當(dāng) n為1的時候，公式就化解為 x = z，

這就意味著，從頭結(jié)點(diǎn)出發(fā)一個指針，從相遇節(jié)點(diǎn) 也出發(fā)一個指針，這兩個指針每次只走一個節(jié)點(diǎn)， 那么當(dāng)這兩個指針相遇的時候就是 環(huán)形入口的節(jié)點(diǎn)。

也就是在相遇節(jié)點(diǎn)處，定義一個指針index1，在頭結(jié)點(diǎn)處定一個指針index2。

讓index1和index2同時移動，每次移動一個節(jié)點(diǎn)， 那么他們相遇的地方就是 環(huán)形入口的節(jié)點(diǎn)。

那么 n如果大于1是什么情況呢，就是fast指針在環(huán)形轉(zhuǎn)n圈之后才遇到 slow指針。

其實(shí)這種情況和n為1的時候 效果是一樣的，一樣可以通過這個方法找到 環(huán)形的入口節(jié)點(diǎn)，只不過，index1 指針在環(huán)里 多轉(zhuǎn)了(n-1)圈，然后再遇到index2，相遇點(diǎn)依然是環(huán)形的入口節(jié)點(diǎn)。

環(huán)形鏈表II代碼：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指針相遇，此時從head 和 相遇點(diǎn)，同時查找直至相遇
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回環(huán)的入口
            }
        }
        return NULL;
    }
};

好！按照老樣子，接下來開始詳細(xì)講解每行代碼的用處，以及為什么這樣寫！

ListNode* fast = head;
ListNode* slow = head;

//設(shè)置兩個指針，分別是快指針和慢指針，并且同時指向頭節(jié)點(diǎn)。

while(fast != NULL && fast->next != NULL)

//這里判斷快指針，為什么不判斷慢指針呢？
因?yàn)?code>快指針一次移動為兩步，是慢指針的兩倍，所以直接判斷快指針即可。
同時因?yàn)榭熘羔樢淮我苿訛閮刹?，所以在移動之前需要判?code>快指針的后兩個節(jié)點(diǎn)是否為空。

slow = slow->next;
fast = fast->next->next;

//開始移動快指針和慢指針

if (slow == fast)

//代表已經(jīng)證明有環(huán)，也證明快指針和慢指針現(xiàn)在已經(jīng)相遇

ListNode* index1 = fast;
ListNode* index2 = head;

//既然快指針和慢指針現(xiàn)在已經(jīng)相遇，我們就開始尋找環(huán)的入口點(diǎn)，即設(shè)置index1指向相遇點(diǎn)處，index2指向頭節(jié)點(diǎn)處。

 while (index1 != index2) {
	 index1 = index1->next;
	 index2 = index2->next;
}

//當(dāng)index1和index2開始相遇的時候代表此時指向的是環(huán)的入口處。

 return NULL;

//如果沒有環(huán)，則返回NULL

補(bǔ)充

在推理過程中，大家可能有一個疑問就是：為什么第一次在環(huán)中相遇，slow的 步數(shù) 是 x+y 而不是 x + 若干環(huán)的長度 + y 呢？

首先slow進(jìn)環(huán)的時候，fast一定是先進(jìn)環(huán)來了。

如果slow進(jìn)環(huán)入口，fast也在環(huán)入口，那么把這個環(huán)展開成直線，就是如下圖的樣子：

那又有一個問題，為什么fast不能跳過去呢？ 在剛剛已經(jīng)說過一次了，fast相對于slow是一次移動一個節(jié)點(diǎn)，所以不可能跳過去。

結(jié)束語

如果覺得這篇文章還不錯的話，記得點(diǎn)贊 ，支持下?。。?span toymoban-style="hidden">文章來源地址http://www.zghlxwxcb.cn/news/detail-453158.html

到了這里，關(guān)于看完這篇文章你就徹底懂啦｛保姆級講解｝-----（LeetCode刷題142環(huán)形鏈表II） 2023.4.24的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！