题目描述

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

当不存在公共节点时，返回空节点。

样例
给出两个链表如下所示：

A：        a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

输出第一个公共节点c1

算法

过程：
让两个指针p、q分别指向两个链表的开头，然后开始遍历，遍历完自己对应那个链表的时候，在指向另外一个链表的开头。
可知：
1. 当两个链表相同长的时候，p、q必然会同时指向相同的元素。
2. 当链表不同长的时候，在经历过一轮之后也会在相同的位置相遇，然后直到遍历相同的元素。

图解：

注意点

1. 相同的元素是指两个指针遍历到_相同的地址_的时候！这个千万小心，我一开始自己模拟的时候，总是认为两个相等的元素就是相同的结点。
2. 输入格式的问题。这个我其实到现在还是没搞懂。这里说一下，如果有大佬知道的，麻烦告知一下，感激不尽！
   按照y总的讲解：

输入包括三行，例如：

[a, b, c, d, e]
[f, g, h]
3
表示的两个链表分别是：

第一个链表即输入第一行的链表：[a, b, c, d, e]
第二个链表即将输入第二行的链表接到第一行链表的第3个节点后面（链表节点下标从1开始）：[a, b, c, f, g, h]
如果输入第三行为-1，表示两个链表不相交，此时第二个链表即输入第二行的链表：[f, g, h]

那么题中的讲解两个链表应该是：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7]
（从一个链表的第10个开始继续往后插入）
但是，测试输出的链表（代码在下方）确实这样:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 10 11 12 13 14
(这个显然就是从第一个链表的第10个元素往后所有元素全部拿过来插入到第二条链表的后面，跟y总讲解的输入格式
有点出入)

时间复杂度

O(n)

参考文献

y总

C++ 代码

class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        //p指针指向a头结点，q指针指向b头结点
        auto p = headA , q = headB;

        /*测试输出两条链表的代码：
        while(p) cout<<p->val<<' ' , p = p-> next;
        cout<<endl;
        while(q) cout<<q->val<<' ' , q = q-> next;
        */
        //当p，q一直不相等的时候，一直循环，直到找到答案
        while(p != q){
            //p不空，移到当前链表当前位置的下一个结点
            if(p) p = p -> next;
            //否则遍历完A链表之后，就指向B链表的头结点
            else p = headB;
            //q跟p的操作一样，不空一直遍历当前链表，遍历完再从另外一条链表继续遍历
            if(q) q = q -> next;
            else q = headA;

        }
        //最后返回答案
        return p;
    }
};

/*
对于while循环中代码简洁一点：
while(p != q){
//三目运算符：p不空就指向下一个结点；p空指向headB链表的头结点。q同理
    p = p ? p->next : headB;
    q = q ? q->next : headA;
}
*/