IT工程師數位筆記本

題目描述
輸入兩個鏈表，找出它們的第一個公共結點。

這題目是指針相關的題目。初步要判斷出來，有公共節點的兩個指針，應當是鏈表后半部分相同。這樣的話，當遇到第一個相同節點（不是node的val相同，而是node完全相同），則找到了結果。

網上找到一種很簡介的寫法。稍微分析了下，其實就是將兩個鏈表L1和L2進行了拼接，得到L1+L2和L2+L1兩個拼接結果。這兩個長度相同，那么one node by one node做判斷就好了。

struct ListNode{
    int val;
    struct ListNode* next;
    ListNode(int x) :val(x), next(NULL){
    }
};

class Solution_8{
public:
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2){
        ListNode* p1 = pHead1;
        ListNode* p2 = pHead2;
        while (p1 != p2){
            
            if (p1 == NULL){
                cout << "p1 is NULL";
            }
            else{
                cout << "p1 is " << p1->val;
            }
            cout << ", ";
            if (p2 == NULL){
                cout << "p2 is NULL";
            }
            else{
                cout << "p2 is " << p2->val;
            }
            cout << endl;

            p1 = (p1 == NULL ? pHead2 : p1->next);
            p2 = (p2 == NULL ? pHead1 : p2->next);
        }
        return p1;
    }
};

第一眼看到這么短的代碼不敢相信答案是對的。然后手動試著模擬運行了幾個樣例，發現是沒有問題的。

第一種情況：有相同節點
L1:1 2 3 4 5
L2:3 4 5
因為兩個鏈表每次都是移動一個步長，盡管兩個鏈表長度往往不一樣，但是L1拼接L2、L2拼接L1，這兩種拼接后的鏈表長度是一致的，就很容易發現相同節點了。

第二種情況：沒有相同節點
那么上一種情況的做法，會使得最終找到的節點是NULL，也就是分別到了“拼接后的鏈表尾部”。

測試一下吧：

int main_Solution_8_1(){
    ListNode* n1 = new ListNode(1);
    ListNode* n2 = new ListNode(2);
    ListNode* n3 = new ListNode(3);
    ListNode* n4 = new ListNode(4);
    ListNode* n5 = new ListNode(5);
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n5;

    Solution_8 s = Solution_8();
    ListNode* res = s.FindFirstCommonNode(n1, n2);
    cout << res->val << endl;
    return 0;
}

int main_Solution_8_2(){
    ListNode* n1 = new ListNode(1);
    ListNode* n2 = new ListNode(2);
    ListNode* n3 = new ListNode(3);
    ListNode* n4 = new ListNode(4);
    ListNode* n5 = new ListNode(5);
    ListNode* n6 = new ListNode(6);
    ListNode* n7 = new ListNode(7);
    n1->next = n2;
    n2->next = n3;

    n4->next = n5;
    n5->next = n6;
    n6->next = n7;

    Solution_8 s = Solution_8();
    ListNode* res = s.FindFirstCommonNode(n1, n4);
    if (res != NULL){
        cout << res->val << endl;
    }
    else{
        cout << "res is NULL " << endl;
    }
    return 0;
}

int main(){
    main_Solution_8_2();
    return 0;
}