前言

歡迎來到小K的Leetcode|代碼隨想錄|專題化專欄，今天將為大家?guī)礞湵硐嘟缓铜h(huán)形鏈表 II的分享?

面試題 02.07. 鏈表相交

?題目鏈接點(diǎn)這里

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

圖示兩個(gè)鏈表在節(jié)點(diǎn) c1 開始相交：

題目數(shù)據(jù) 保證 整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。
注意，函數(shù)返回結(jié)果后，鏈表必須 保持其原始結(jié)構(gòu) 。

示例 1：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at ‘8’
解釋：相交節(jié)點(diǎn)的值為 8 （注意，如果兩個(gè)鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。
在 A 中，相交節(jié)點(diǎn)前有 2 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)。

示例 2：

輸入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at ‘2’
解釋：相交節(jié)點(diǎn)的值為 2 （注意，如果兩個(gè)鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [0,9,1,2,4]，鏈表 B 為 [3,2,4]。
在 A 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 1 個(gè)節(jié)點(diǎn)。

示例 3：

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

提示：

listA 中節(jié)點(diǎn)數(shù)目為 m
listB 中節(jié)點(diǎn)數(shù)目為 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 沒有交點(diǎn)，intersectVal 為 0
如果 listA 和 listB 有交點(diǎn)，intersectVal == listA[skipA + 1] == listB[skipB + 1]
思路：這道題目也是雙指針的一種用法，我們先定義兩個(gè)指針分別指向兩個(gè)鏈表的頭結(jié)點(diǎn)，然后讓指向較長(zhǎng)鏈表的指針朝后移動(dòng)，和較短鏈表的那個(gè)指針對(duì)其，最后就是移動(dòng)，循環(huán)比較，返回第一個(gè) 兩個(gè)指針指向同一節(jié)點(diǎn)的情況，沒找到則返回空

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA, *curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != nullptr) {
            lenA++;
            curA = curA->next;
        }
        while (curB != nullptr) {
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        if (lenA < lenB){
            swap(lenA,lenB);
            swap(curA,curB);
        }
        int gap = lenA - lenB;
        while (gap--) curA = curA->next;
        while (curA != nullptr) {
            if(curA == curB) return curA;
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;
    }
};

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

?題目鏈接點(diǎn)這里
給定一個(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í)際情況。
不允許修改 鏈表。

示例 1：

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

示例 2：

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

示例 3：

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

提示：
鏈表中節(jié)點(diǎn)的數(shù)目范圍在范圍 [0, 104] 內(nèi)
-105 <= Node.val <= 105
pos 的值為 -1 或者鏈表中的一個(gè)有效索引

思路：解決這個(gè)問題我們需要明確下面兩個(gè)問題

• 判斷鏈表是否有環(huán)
• 如果有環(huán)，如何找到這個(gè)環(huán)的入口

問題一：判斷鏈表是否有環(huán)

可以使用快慢指針法，定義一個(gè)快指針 fast 和一個(gè)慢指針 slow ，從頭結(jié)點(diǎn)開始，每次讓快指針移動(dòng)兩個(gè)節(jié)點(diǎn)，慢指針每次移動(dòng)一個(gè)節(jié)點(diǎn)，如果在途中相遇，則代表有環(huán)

相遇一定在環(huán)內(nèi)相遇，這是為什么？快指針一定比慢指針先入環(huán)
為什么快慢指針一定會(huì)相遇？快指針一次移動(dòng)兩步，而慢指針一次移動(dòng)一步，所以快指針相當(dāng)于是以每次一步來追趕慢指針，所以一定會(huì)相遇

問題二：找環(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。
那么相遇時(shí)： 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)的個(gè)數(shù)A
則有：(x + y) * 2 = x + y + n (y + z)
化簡(jiǎn)得x = (n - 1)(y + z) + z ，注意這里n一定是大于等于1的，因?yàn)?fast指針至少要多走一圈才能相遇slow指針。當(dāng)n等于一和大于一的效果是一樣的，因?yàn)楫?dāng)n大于一就相當(dāng)于快指針在環(huán)內(nèi)多轉(zhuǎn)了幾圈

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode* index1 = head;
                ListNode* index2 = fast;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return nullptr;
    }
};

總結(jié)

今天的收獲還是挺大的，這個(gè)環(huán)形鏈表不難，但是很有意思，有點(diǎn)寫數(shù)學(xué)題的感覺，一步一步揭開面紗真的很舒服~文章來源地址http://www.zghlxwxcb.cn/news/detail-581100.html

到了這里，關(guān)于【代碼隨想錄 | Leetcode | 第七天】鏈表 | 鏈表相交 | 環(huán)形鏈表 II的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！