前言：本篇博客將講解三個OJ題，前兩個作為鋪墊，最后完成環(huán)形鏈表的節(jié)點的尋找

一、160. 相交鏈表

題目鏈接：LeetCode—相交鏈表

題目描述：
給你兩個單鏈表的頭節(jié)點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節(jié)點。如果兩個鏈表不存在相交節(jié)點，返回 null 。
圖示兩個鏈表在節(jié)點 c1 開始相交：

注意，函數(shù)返回結果后，鏈表必須 保持其原始結構 。
評測系統(tǒng)將根據(jù)這些輸入創(chuàng)建鏈式數(shù)據(jù)結構，并將兩個頭節(jié)點 headA 和 headB 傳遞給你的程序。如果程序能夠正確返回相交節(jié)點，那么你的解決方案將被 視作正確答案 。

示例1：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at ‘8’
解釋：相交節(jié)點的值為 8 （注意，如果兩個鏈表相交則不能為 0）。

示例2：

輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
由于這兩個鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
這兩個鏈表不相交，因此返回 null 。

題目解析:

1. 遍歷鏈表計算長度： 初始化兩個指針curA和curB分別指向鏈表headA和headB的頭節(jié)點，然后遍歷鏈表，分別計算鏈表的長度lenA和lenB，來到尾節(jié)點時比較是否一致，一致說明鏈表相交；否則，不相交，即可返回NULL。
2. 對齊起點：如果尾節(jié)點相同，計算兩個鏈表長度的差值n，然后選取較長鏈表的頭節(jié)點為longList，較短鏈表的頭節(jié)點為shortList。然后，將longList指針向后移動n個位置，使得兩個鏈表剩余長度相等。
3. 尋找交點： 同時遍歷longList和shortList，找到它們第一個相同的節(jié)點，即為交點。

代碼實現(xiàn)：

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    ListNode* curA = headA, *curB = headB;
    // 初始化鏈表headA和headB的長度分別為1，原因是curA和curB初始化就指向頭
    int lenA = 1, lenB = 1;

    // 計算鏈表headA的長度
    while (curA->next) {
        lenA++;
        curA = curA->next;
    }

    // 計算鏈表headB的長度
    while (curB->next) {
        lenB++;
        curB = curB->next;
    }

    // 如果鏈表headA和headB的尾節(jié)點不相同，說明它們沒有交點，返回NULL
    if (curA != curB) {
        return NULL;
    }

    //abs 函數(shù)是 C 語言標準庫（<stdlib.h> 頭文件）中的一個函數(shù)，用于返回整數(shù)的絕對值
    int n = abs(lenA - lenB);
    // 初始化指針longList和shortList，分別指向較長和較短的鏈表頭部
    ListNode* longList = headA, *shortList = headB;

    // 如果鏈表headA較短，調(diào)整longList和shortList的指向
    if (lenA < lenB) {
        longList = headB;
        shortList = headA;
    }

    // 將較長鏈表指針向后移動，使兩個鏈表剩余長度相等
    while (n--) {
        longList = longList->next;
    }

    // 同時移動長鏈表和短鏈表指針，直到找到交點
    while (longList != shortList) {
        longList = longList->next;
        shortList = shortList->next;
    }

    // 返回交點（如果存在）
    return longList;
}

二、141. 環(huán)形鏈表

題目鏈接：LeetCode—環(huán)形鏈表

題目描述：
給你一個鏈表的頭節(jié)點 head ，判斷鏈表中是否有環(huán)。
如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。
注意：pos 不作為參數(shù)進行傳遞 。僅僅是為了標識鏈表的實際情況。
如果鏈表中存在環(huán) ，則返回 true 。 否則，返回 false 。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。

示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)。

題目解析：
這是經(jīng)典的快慢指針算法用于檢測鏈表中是否存在環(huán)。算法的核心思想是使用兩個指針，一個移動速度較慢（每次移動一步），另一個移動速度較快（每次移動兩步）。如果鏈表中存在環(huán)，快指針最終會追上慢指針，導致它們相遇。

在遍歷過程中，如果快指針能夠追上慢指針，就說明存在環(huán)。如果沒有相遇，而是快指針達到鏈表的末尾（為NULL），則鏈表是無環(huán)的。

這種算法的時間復雜度為 O(N)，其中 N 是鏈表的長度。這是因為在最壞情況下，快指針將遍歷整個鏈表一次。

代碼實現(xiàn)：

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    // 初始化兩個指針，slow每次移動一步，fast每次移動兩步
    ListNode* slow = head;
    ListNode* fast = head;

    // 遍歷鏈表，直到fast為NULL或fast的下一個節(jié)點為NULL
    while (fast != NULL && fast->next != NULL) {
        // slow前進一步
        slow = slow->next;
        // fast前進兩步
        fast = fast->next->next;

        // 如果存在環(huán)，slow和fast會在某個時刻相遇
        if (slow == fast) {
            // 存在環(huán)，返回true
            return true;
        }
    }

    // 遍歷完成，沒有相遇，說明鏈表無環(huán)
    return false;
}

思考問題：快慢指針的速度有要求嗎，會不會存在快指針和慢指針不相遇的情況。

首先說結論，只要有速度差，都可以相遇。

想象一下，快慢指針相遇時，它們在環(huán)內(nèi)，且快指針比慢指針多走了n個環(huán)，C是環(huán)的大小，我們令快指針的速度為a，慢指針的速度為b。

假設快慢指針走k步，它們相遇。又因為相遇時，快指針比慢指針多走了n個環(huán)。我們可以得到 $(a?b)k=nC$。

我們從題中得知a-b和C，k和n是未知數(shù)。易知一定存在整數(shù)k和整數(shù)n使得等式成立。得出結論，快慢指針一定能在環(huán)內(nèi)相遇。

三、142. 環(huán)形鏈表II

題目鏈接：LeetCode—環(huán)形鏈表II
經(jīng)過前兩題的鋪墊，這題的思路更容易打開了

題目描述：
給定一個鏈表的頭節(jié)點 head ，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。
如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。
注意：pos 不作為參數(shù)進行傳遞，僅僅是為了標識鏈表的實際情況。
不允許修改 鏈表。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

示例 3：

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環(huán)。

題目解析：

判斷是否有環(huán)： 快指針速度設為2，慢指針設為1（為了找入環(huán)節(jié)點必須這樣設置，下面會闡述原因），無環(huán)直接返回NULL。

找入環(huán)節(jié)點： 快指針速度設為2，慢指針設為1的原因在這，想象一下，在極端情況下，快慢指針同時從入環(huán)節(jié)點出發(fā)（可以看作快指針與慢指針相距一個環(huán)的距離）。這種情況下，慢指針走了半環(huán)，快指針走了一個環(huán)；接著慢指針走完剩下半個環(huán)來到入環(huán)點，這時快指針又走了一個環(huán)來到入環(huán)點。快慢指針在入環(huán)節(jié)點相遇了。

在實際情況下，快指針一定先入環(huán)，接著慢指針從頭節(jié)點到達入環(huán)節(jié)點，這時快慢指針的距離一定小于或等于環(huán)。那么可想而知，它們相遇時，慢指針最多走完一次環(huán)，快指針在從慢指針入環(huán)到它們相遇時也最多走完兩次環(huán)。 我們設相遇時距離入環(huán)節(jié)點為X，C時環(huán)的大?。╔<=C）。

相遇時有等式 $2(L+X)=L+n?C+X$ （快指針的路程=L+從頭節(jié)點到相遇時走了n次環(huán)+X，慢指針的路程=L+X）。化簡得 $L=(n?1)?X+C?X$,從公式中我們可以看出，當我們走完L（到達入環(huán)節(jié)點），等于從距離入環(huán)節(jié)點的X處開始走，可以走（n-1）次環(huán)加上C-X（到達入環(huán)節(jié)點）。

因此，用兩個相同速度的指針，一個從頭節(jié)點開始走，另一個從相遇點開始走，最終會在入環(huán)節(jié)點相遇。

代碼實現(xiàn)：

typedef struct ListNode ListNode;

struct ListNode *detectCycle(struct ListNode *head) {
    // 初始化兩個指針，slow每次移動一步，fast每次移動兩步
    ListNode* slow = head;
    ListNode* fast = head;

    // 遍歷鏈表，直到fast為NULL或fast的下一個節(jié)點為NULL
    while (fast && fast->next) {
        // slow前進一步
        slow = slow->next;
        // fast前進兩步
        fast = fast->next->next;

        // 如果存在環(huán)，slow和fast會在某個時刻相遇
        if (slow == fast) {
            // 相遇點保存在meet中，從鏈表頭開始和meet同時移動，直到再次相遇，即為環(huán)的起點
            ListNode* meet = slow;
            while (head != meet) {
                head = head->next;
                meet = meet->next;
            }
            // 返回環(huán)的起點
            return meet;
        }
    }

    // 遍歷完成，沒有相遇，說明鏈表無環(huán)
    return NULL;
}

如果你喜歡這篇文章，點贊??+評論+關注??哦！
歡迎大家提出疑問，以及不同的見解。文章來源地址http://www.zghlxwxcb.cn/news/detail-754372.html

到了這里，關于【刷題專欄—突破思維】LeetCode 142. 環(huán)形鏈表 II的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！