題目

給你兩個單鏈表的頭節點 headA 和 headB ，請你找出并回傳兩個單鏈表相交的起始節點，如果兩個鏈表沒有交點，回傳 null ，圖示兩個鏈表在節點 c1 開始相交：

題目資料 保證 整個鏈式結構中不存在環，
注意，函式回傳結果后，鏈表必須 保持其原始結構 ，

鏈接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/

分析

我們在拿到這道題目時，我們的第一反應一一遍歷兩個鏈表，只要兩個指標指向的元素地址相同我們就找到了兩個鏈表相交的結點，

但我們現在面臨一個問題，我們在創建兩個指標分別指向兩個鏈表遍歷時，因為每個鏈表的長度可能不一樣，那么我們就可能會造成就算兩個鏈表相連，我們兩個指標在遍歷的時候也不可能相遇

那么我們應該然后解決這個問題呢？

那么這個時候我們可以采用這種解決方法來實作，我們想分別計算出每個鏈表的長度，然后我們計算兩個鏈表長度的差值，我們讓較長鏈表的指標先向后移動差值的單位距離，之后我們在同時遍歷我們的兩個鏈表，當我們的兩個指標指向的節點地址相同時，我們就找到了相交的節點，

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {

    struct ListNode* n1 = headA;
    struct ListNode* n2 = headB;
    int l1 = 0;
    int l2 = 0;
    int gap = 0;

    while(n1)//計算我們第一個鏈表的長度
    {
        l1++;
        n1 = n1->next;
    }
    while(n2)//計算我們第二個鏈表的長度
    {
        l2++;
        n2 = n2->next;
    }

    if(l1 > l2)//判讀那個鏈表長，然后將長的鏈表移動長度的差值
    {
        gap = l1 - l2;
        while(gap--)
        {
            n1 = n1->next;
        }
    }

    if(l2 > l1)
    {
        gap = l2 - l1;
        while(gap--)
        {
            n2 = n2->next;
        }
    }
    while(n1 && n2)//開始同時遍歷我們的鏈表
    {
        if(n1 == n2)
        {
            return n1;
        }
        else
        {
            n1 = n1->next;
            n2 = n2->next;
        }
    }
    return NULL;
    
}

這個時候我們看似實作了我們的題目要求，可當我們運行代碼時，我們得出

這里提醒我們有空值的出現，使得在移動長鏈表時移動失敗，這個時候我們回看代碼，發現我們在前面獲取兩個鏈表的長度時，已經將兩個鏈表的指標移動到了最后一個節點的位置，所以會提醒我們會有空值的情況出現

這個時候我們可以在創建兩個指標再一次指向我們的兩個鏈表，創建時間為當我們得出兩個鏈表的長度后，我們再創建這兩個指標，然后我們開始后續的操作

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {

    struct ListNode* n1 = headA;
    struct ListNode* n2 = headB;
    int l1 = 0;
    int l2 = 0;
    int gap = 0;

    while(n1)
    {
        l1++;
        n1 = n1->next;
    }
    while(n2)
    {
        l2++;
        n2 = n2->next;
    }

    struct ListNode* nn1 = headA;
    struct ListNode* nn2 = headB;

    if(l1 > l2)
    {
        gap = l1 - l2;
        while(gap--)
        {
            nn1 = nn1->next;
        }
    }

    if(l2 > l1)
    {
        gap = l2 - l1;
        while(gap--)
        {
            nn2 = nn2->next;
        }
    }
    while(nn1 && nn2)
    {
        if(nn1 == nn2)
        {
            return nn1;
        }
        else
        {
            nn1 = nn1->next;
            nn2 = nn2->next;
        }
    }
    return NULL;
    
}

我們將代碼優化一下，使代碼的可讀性更強一些（我們將代碼中指標的創建命名更易懂）

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    int lenA = 0,lenB = 0;

    while(curA)
    {
        lenA++;
        curA = curA->next;
    }
     while(curB)
    {
        lenB++;
        curB = curB->next;
    }

    struct ListNode * ListLong = headA;
    struct ListNode * ListShort = headB;
    if(lenA < lenB)
    {
        ListLong = headB;
        ListShort = headA;
    }

    int gap = abs(lenA - lenB);

    while(gap--)
    {
        ListLong = ListLong -> next;
    }

    while(ListLong && ListShort)
    {
        if(ListLong == ListShort)
        {
            return ListLong;
        }
        else
        {
            ListLong = ListLong -> next;
            ListShort = ListShort -> next;
        }
    }
    return NULL;
}

代碼

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    int lenA = 0,lenB = 0;

    while(curA)
    {
        lenA++;
        curA = curA->next;
    }
     while(curB)
    {
        lenB++;
        curB = curB->next;
    }

    struct ListNode * ListLong = headA;
    struct ListNode * ListShort = headB;
    if(lenA < lenB)
    {
        ListLong = headB;
        ListShort = headA;
    }

    int gap = abs(lenA - lenB);

    while(gap--)
    {
        ListLong = ListLong -> next;
    }

    while(ListLong && ListShort)
    {
        if(ListLong == ListShort)
        {
            return ListLong;
        }
        else
        {
            ListLong = ListLong -> next;
            ListShort = ListShort -> next;
        }
    }
    return NULL;
}

總結

鏈表相交問題中，我們在計算兩個鏈表的長度時，指標已經指向里鏈表的最后一個元素，而我們如果再繼續執行后面的代碼，那么我們就會造成本題中出現的空值問題，這一點需要以后在解決問題中多加注意

以上就是我對這道題目的個人理解

上述內容如果有錯誤的地方，還麻煩各位大佬指教【膜拜各位了】【膜拜各位了】