舍友洗了個澡，我就解決了相交連結串列問題

題目要求

連結：160. 相交連結串列 - 力扣（LeetCode） (leetcode-cn.com)

---

---

注意：相交連結串列是Y形狀的，不是X形狀的。一個結點只有一個next指向

---

如何判斷相交：

方法：比較兩個連結串列的尾結點地址是否一致

---

相交和不相交的不同之處

相交：兩個連結串列從相交結點開始，後面的結點的地址一致==>尾結點相同

不相交：兩個連結串列的所有結點的地址都是不相同的

---

所以只需要遍歷兩個連結串列，找到兩個連結串列的尾結點，然後比較是否相等。如果相等則進行下一步，找相交起始節點。如果不相等 -> 直接返回NULL

//找兩個連結串列的尾
while(tailA->next != NULL)
{}
while(tailB->next != NULL)
{}
//判斷是否相等
if(tailA != tailB)
{
    return false;
}

---

如果相交，如何找到相交起始結點

錯誤思路：

同時遍歷兩個連結串列，比較對應結點的地址是否一致

不可行原因：

兩個連結串列的長度不一樣，如果二者在相交結點前的長度一致，則可以這樣比較(這也是後面思路2的想法)

若相交結點前，兩個連結串列的長度不一致，則不可行！

---

思路1：

若兩個連結串列相交，則它們至少有一個結點的地址相同(從相交起始結點向後，結點的地址都相同)

• A連結串列中的每個結點分別和B連結串列中的所有結點進行地址比較

  • 用cur遍歷A連結串列，B連結串列每次進入迴圈都從頭開始遍歷

  • 如果結點地址相同，該結點就是開相交結點，返回該位置即可

  • 如果不相同，繼續比較。

• 迴圈結束條件：A連結串列的所有結點都比較結束，即cur為NULL跳出迴圈。比較完了都沒有返回->說明不相交

---

當然，也可以用B連結串列的每個結點分別和A連結串列中的所有結點進行地址比較

---

時間複雜度分析：假設A連結串列有M個結點，B連結串列有N個結點

時間複雜度為：O(M*N)

---

程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    //如果其中一個連結串列為空，不可能存在相交
    if(headA  == NULL|| headB == NULL)
    {
        return NULL;
   
    //A中的每個結點和B分別比較(B和A比較也可以)，看二者的地址是否一致 
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    while(curA)
    {
        //A連結串列的每個結點和整條B連結串列進行比較
        curB = headB;
        while(curB)
        {
            //地址比較
            if(curA == curB)
            {
                return curA;
            }
            //curB向後移動
            curB = curB ->next;
        }
        //A的下一結點繼續比較
        curA = curA->next;
    }
    //A的結點都比較完了，說明找不到
    return NULL;
}

---

思路2：

• 上面判斷相交得過程，可以分別把兩個連結串列的長度也求出來，記為lenA和lenB

  • 注意：標誌二者長度的變數要初始化為1(因為如果只有一個結點，是不會進入迴圈的)

• 求出兩個連結串列的長度差記為gap， 由於不知道是lenA大還是lenB更大，所以可以使用求絕對值的函數abs求出gap

• 長連結串列先走gap步，然後二者再一起走，比較二者的結點的地址是否一致，第一個地址相同的結點就是相交結點

  • 可以先假設一個連結串列是長連結串列,另一個是短連結串列。然後再根據長度判斷假設是否合理

---

圖解：

---

注意：短連結串列和長連結串列可能是一條鏈

---

程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    //其中一個連結串列為空->不相交
    if(headA == NULL|| headB == NULL)
    {
        return NULL;
    }

    //如果相交：尾結點相同
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    int lenA = 1;//不能初始化為0,如果只有一個結點，不進入迴圈
    int lenB = 1;//和上面同理
    
    //遍歷找兩個連結串列的尾,順便求兩個連結串列的長度
    while(tailA->next !=NULL)
    {
        lenA +=1;
        tailA = tailA->next;
    }
     while(tailB->next !=NULL)
    {
        lenB +=1;
        tailB = tailB->next;
    }

    //判斷尾結點是否一致,不一致則不相交
    if(tailA != tailB)
    {
        return NULL;
    }
    //計算出兩個連結串列長度的差值為gap
    int gap = abs(lenA - lenB);//未知誰大，所以求絕對值
    //長連結串列先走gap步，二者再一起走找交點
    //假設一個連結串列長
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    //判斷假設是否成立：
    //lenA < lenB 說明假設不成立，B連結串列更長
    if(lenA < lenB)
    {
        longList = headB;
        shortList = headA;
    }
    //長連結串列先走gap步
    while(gap--)
    {
        longList = longList -> next;
    }
    //二者再同時走,二者相等就是相交點
    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    //當longList == shortList時跳出迴圈，此時二者指向的就是起始相交結點
    
    //如果是不相交的，上面就尾結點不同就已經返回了
    //程式碼能到指向這說明兩個連結串列就是相交的
    return shortList;
}