舍友洗了個澡，我就解決了相交鏈表問題

題目要求

鏈接：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;
}