《剑指offer》-链表的第一个公共节点

题目描述
输入两个链表，找出它们的第一个公共结点。

这题目是指针相关的题目。初步要判断出来，有公共节点的两个指针，应当是链表后半部分相同。这样的话，当遇到第一个相同节点（不是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;
}