人森很精彩，所以要把所有事情都記起來=ˇ=

這題是easy，只是我覺得我很有障礙

題目會給你兩個ListNode*的root，要你找出他們開始重疊的那一個node，沒有就回傳nullptr

比如說：

begin to intersect at node c1.

差不多是這樣，應該沒什麼問題，只是我腦袋有問題

Sol：

因為考慮到A和B兩個重疊前的長度不一樣

我一開始是直接用一個set來記錄出現過的node，然後一個一個比較

邏輯滿簡單的，大概是這樣：

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> NodeSet;
        
        while (headA != nullptr || headB != nullptr)
        {
            if (headA != nullptr)
            {
                if (NodeSet.count(headA))
                {
                    return headA;
                }
                
                NodeSet.emplace(headA);
                headA = headA->next;
            }
            
            if (headB != nullptr)
            {
                if (NodeSet.count(headB))
                {
                    return headB;
                }
                
                NodeSet.emplace(headB);
                headB = headB->next;
            }
        }
        
        return nullptr;
    }

不過後來發現這作法在執行速度跟耗費資源都是滿慘的...

於是我去看了一下其他人的方法，發現我有一個盲點

就是第一句話：考慮到A和B兩個重疊前的長度不一樣

那何不把他們用成一樣呢...

沒錯，我們可以先算A和B的長度

因為多出來那段根本不可能重疊，所以完全不用考慮那段

可以直接一個loop就找出重疊的那個

大概長成這樣：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr)
            return NULL;
        
        int lenA = listLen(headA); // 計算A和B的長度
        int lenB = listLen(headB);
        
        if (lenA >= lenB) // 算出差並且移動那個ListNode到要開始比較的node
        {
            int dis = lenA - lenB;
            while (dis > 0)
            {
                headA = headA->next;
                --dis;
            }
        }
        else
        {
            int dis = lenB - lenA;
            while (dis > 0)
            {
                headB = headB->next;
                --dis;
            }
        }
        
        while (headA!=nullptr && headB!= nullptr) // 開始比較
        {
            if(headA == headB)
                return headA;
            headA = headA->next;
            headB = headB->next;
        }
    
        return NULL;
    }
    
    int listLen(ListNode *head){
        if (head == nullptr)
            return 0;
        
        int len = 0;
        while (head != nullptr)
        {
            ++len;
            head = head->next;
        }
        
        return len;
    }

這裡有個點要釐清一下

listLen(int ListNode* head) 雖然是傳指標進去，不過並不會影響到外面傳進去的值

因為裡面賦值的不是那個指標的位址，而是那個指標，如果你把傳進去的指標當成一個正常的變數來看，就能夠理解了

實際上指標也就是變數啦XD

那這題就這樣囉~ 下題再見XD