題型三：鏈表相交，找相交節(jié)點

思路解析

看到這類題型首先要判斷鏈表是否相交，而相交條件：兩鏈尾部節(jié)點相同（地址相同，val值相同，next相同）。這樣我們便可找到兩鏈表的尾節(jié)點并判斷這兩個節(jié)點地址是否相同，若相同則兩鏈表相交。上面這種情況兩鏈表呈'Y'型，那么我們想一下兩鏈表相交是否可以呈'X'型呢？

如上圖所示如果兩鏈表相交呈'X'型的話，相交節(jié)點的next就會指向兩個節(jié)點，這并不符合單鏈表的定義。
那么在判斷了相交鏈表后，如何找到相交節(jié)點呢？在我們找尾節(jié)點時，我們可以順便計算兩鏈表的長度，定義兩鏈表指針slow，fast分別指向鏈表頭節(jié)點，讓指向長鏈表的指針先走兩鏈表長度的差值，然后一起向后走，當(dāng)slow == fast時就找到了相交節(jié)點。

OJ題實例

LeetCode鏈接: 160. 相交鏈表

解題代碼

//方法一的解法
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
    struct ListNode* cur1 = headA, *cur2 = headB;
    int len1 = 1, len2 = 1;
    //找尾節(jié)點，并計算鏈表長度
    while(cur1 -> next)
    {
        cur1 = cur1->next;
        len1++;
    }
    while(cur2 -> next)
    {
        cur2 = cur2->next;
        len2++;
    }
    if(cur1 != cur2)
        return NULL;
    //計算鏈表長度差值
    int count = abs(len1 - len2);
    struct ListNode* slow=headA, *fast=headB;
    if(len1 > len2)
    {
        fast = headA;
        slow = headB;
    }
    //找相交節(jié)點
    while(count--)
        fast = fast->next;
    while(slow != fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

題型四：鏈表帶環(huán)，找入環(huán)節(jié)點

思路解析

解決這題我們還是要先定義快慢指針slow，fast，即當(dāng)slow向后走一步，fast向后走兩步。我們便可寫一個結(jié)束條件為fast && fast->next的循環(huán)。因為如果此鏈表不帶環(huán)，那么指針遲早會走到NULL；如果鏈表帶環(huán)，那么便沒有空節(jié)點，此循環(huán)便不會結(jié)束。這時我們只需要在slow == fast時結(jié)束循環(huán)，因為只有環(huán)形結(jié)構(gòu)slow才能追上fast，則鏈表帶環(huán)且這點在環(huán)內(nèi)為相遇點。
對于找入環(huán)的第一個節(jié)點，我們可以先假設(shè)C為環(huán)長，L為環(huán)外面部分長，X為入環(huán)點到相遇節(jié)點的長，n為兩指針相遇時fast比slow多走的圈數(shù)，此處長皆為節(jié)點數(shù)，那么我們便可得到如下圖所示的結(jié)構(gòu)圖：

接下來我將以兩種方法解決此問題：

方法一：
我們可以想到當(dāng)兩節(jié)點相遇時，慢指針slow走過了L + X的距離，快指針fast走過了L + nC + X距離，又因為快指針的速度是慢指針的2倍，于是我們得到了一個數(shù)學(xué)公式，即：2(L + X) = L + nC + X，經(jīng)過化簡最后得到L = nC - X。此時我們可以定義兩個結(jié)構(gòu)體指針head，meet讓他們分別從鏈表頭節(jié)點和相遇節(jié)點向后走，根據(jù)此公式他們會在入環(huán)的第一節(jié)點相遇，于是就找到了入環(huán)第一個節(jié)點。

方法二：
我們可以在相遇點處將鏈表切斷，然后經(jīng)過反轉(zhuǎn)鏈表的到'Y'型，于是乎這題就轉(zhuǎn)變?yōu)榱祟}型三的類型，即相交鏈表找第一個相交節(jié)點，如下所示：

有兩點需要注意：

1. 如圖中1處，我們是將L + X的部分反轉(zhuǎn)；
2. 如圖中2處，最后需要將指向原頭位置的指針指向NULL。

OJ實例

LeetCode鏈接: 142. 環(huán)形鏈表 II文章來源地址http://www.zghlxwxcb.cn/news/detail-752969.html

解題代碼

//基于方法一的解法：
struct ListNode *detectCycle(struct ListNode *head)
{
   struct ListNode* slow = head, *fast = head;
   //判斷fast和slow相遇的地方
   while(fast && fast->next)
   {
       slow = slow->next;
       fast = fast->next->next;
       if(fast == slow)
           break;
   }
   if(fast == NULL || fast -> next == NULL)
       return NULL;
    struct ListNode* meet = slow;
    //2(L+X) = L+nC+X
    //L+X=nC(C為環(huán)長，L為環(huán)外面部分長,X為進環(huán)點到相遇點的距離)
    while(meet != head)
    {
        meet = meet->next;
        head = head->next;
    }
    return meet;
}

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】鏈表經(jīng)典OJ題，常見幾類題型（二）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！