题目描述

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

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