?? 環(huán)形鏈表 I 題目描述

給你一個鏈表的頭節(jié)點 head ，判斷鏈表中是否有環(huán)。如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達，則鏈表中存在環(huán)。
如果鏈表中存在環(huán) ，則返回 true 。 否則，返回 false 。

思路：快慢指針問題。我們可以聲明一個 fast 指針（一次走兩步），聲明一個 slow 指針（一次走一步）。如果鏈表中存在環(huán)，那么 fast 指針和 slow 指針就會相遇，如果相遇則代表有環(huán)，否則 fast 指針會結束代表沒環(huán)。

?? 為什么快指針走兩步，慢指針走一步可以相遇？

圖：

假設 slow 進環(huán)后，fast 和 slow 距離是 $N$。這時候 fast 開始追擊 slow ，fast 一次走兩步，slow一次走一步，他們之間的距離每次縮小 $1$。N、N-1、N-2、...、2、1、0。最終他們相遇了，所以結論是肯定會相遇，因為他們的距離每次縮小$1$。

?? 那快指針一次走三步，慢指針走一步可以相遇嗎？

還是假設 slow 進環(huán)后，fast 和 slow 距離是 $N$。這時候 fast 一次走三步，slow 一次走一步，他們之間的距離每次縮小 $2$。

1. 當 $N$ 是偶數(shù)的情況：N、N-2、N-4、...、4、2、0 相遇追上了。
2. 當 $N$ 是奇數(shù)的情況：N、N-2、N-4、...、3、1、-1。這里 -1 意味著剛好錯過了，但是此時 fast 是要超出 slow 一步，再假設環(huán)的大小是 $C$。那么現(xiàn)在 fast 和 slow 的距離剛好是 $C?1$步。又分為兩種情況：
   • 如果 $C?1$ 是偶數(shù)的話，那么 fast 和 slow 就可以相遇。
   • 如果 $C?1$ 是奇數(shù)的話，那么 fast 就會重復上面是奇數(shù)的情況，永遠不會相遇。

結論：當 fast 一次走三步，slow 一次走一步，不一定可以相遇。

leetcode鏈接：141.環(huán)形鏈表 I

?? 代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-529663.html

bool hasCycle(struct ListNode *head) {
    struct ListNode * slow = head;
    struct ListNode * fast = head;
    
    // 考慮沒有環(huán)的情況下，奇數(shù)和偶數(shù)個鏈表 fast 結束條件不同
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow) {
            return true;
        }
    }

    return false;
}

?? 環(huán)形鏈表 II 題目描述

給定一個鏈表的頭節(jié)點 head ，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 NULL。不允許修改鏈表。
結論是當一個指針從 fast 和 slow 的相遇點 meet 開始走，一個指針從 head 位置開始走，最終 meet 和 head 會在入環(huán)點相遇。

?? 為什么一個指針從相遇點走，一個指針從頭走，他倆會在入環(huán)點相遇呢？

假設 head 到入環(huán)點的距離是 $L$ ，入環(huán)點到相遇點的距離是 $X$，而環(huán)的大小是 $C$。
首先 slow 進環(huán)之后，fast 在一圈之內(nèi)，一定可以追上 slow！因為追擊的過程他們距離每次縮小1，首先排除錯過，而 slow 進環(huán) fast 與其最大長度也只是 $C?1$，所以 slow 最多走不到半圈，fast 就會追上。
slow 走的路程：$L+X$
fast 走的路程：$L+N?C+X$? ?$(N>=1)$ 假設 slow 在進環(huán)前，fast 在環(huán)里轉了 $N$ 圈。

所以 fast 走了 slow 2倍。

• $2?(L+X)=L+N?C+X$
• $L+X=N?C$
• $L=N?C?X$

所以 $L$ 的距離就是繞了 $N$ 圈之后到達 meet 的距離在減去 $X$ 的距離，就是入環(huán)點。
結論：一個指針從 meet 開始走，一個指針從 head 開始走，他們會在入環(huán)點相遇。

leetcode鏈接：142.環(huán)形鏈表 II

?? 代碼：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode * slow = head;
    struct ListNode * fast = head;
    
    // 考慮沒有環(huán)的情況下，奇數(shù)和偶數(shù)個鏈表 fast 結束條件不同
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow) {
             struct ListNode * meet = fast;
             while (head != meet) {
                 head = head->next;
                 meet = meet->next;
             }

             return meet;
        }
    }

    return NULL;
}

到了這里，關于leetcode 141.環(huán)形鏈表 I - 142.環(huán)形鏈表 II 代碼及指針相遇證明問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！