? 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。
? 个人主页：不 良
? 系列专栏：?剑指 Offer  ?Linux
? 学习格言：博观而约取，厚积而薄发
? 欢迎进来的小伙伴，如果小伙伴们在学习的过程中，发现有需要纠正的地方，烦请指正，希望能够与诸君一同成长！ ?

剑指 Offer 52. 两个链表的第一个公共节点

题目：

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

如下面的两个链表：

在节点 c1 开始相交。

示例1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

• 如果两个链表没有交点，返回 null；

• 在返回结果后，两个链表仍须保持原有的结构；

• 可假定整个链表结构中没有循环；

• 程序尽量满足O(N)时间复杂度，且仅用 O(1) 内存。

思路一：

双指针法。

1.先定义两个指针fast和slow分别记录链表中当前节点，再定义两个变量nA和nB用来记录链表中节点个数；

2.然后分别遍历这两个链表，统计链表中节点个数，然后计算出节点个数差值dif并让节点个数多的链表先向前移动dif步；

3.再然后就是让两个指针同时向后移动，当两个指针相等时指针指向的就是两个链表的第一个公共节点。

代码如下：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* fast = headA; //记录A当前节点
        ListNode* slow = headB; //记录B当前节点
        int nA = 0; // A中节点个数
        int nB = 0; // B中节点个数
        //统计A中节点个数
        while(fast)
        {
            nA++;
            fast = fast->next;
        }
        //统计B中节点个数
        while(slow)
        {
            nB++;
            slow = slow->next;
        }
        fast = headA;
        slow = headB;
        int dif = nA - nB;
        //如果nA大于nB，先让fast先向前走dif步
        if(dif > 0)
        {
            while(fast && dif--)
            {
                fast = fast->next;
            }
        }
        //如果nA比nB小，先让slow向前走dif步
        else
        {
            dif = - dif; //dif小于0，-dif大于0
            while(slow && dif--)
            {
                slow = slow->next;
            }
        }
        //然后两个一起走，当两个指针相等时就是两个链表的第一个公共节点
        while(fast && slow && fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

时间复杂度：O(M + N)，M是链表A的长度，N是链表B的长度。

空间复杂度：O(1)

思路二：

哈希集合。

unordered_set容器即无序set容器，和set容器唯一的区别就是set容器会自行对存储的数据进行排序，而unordered_set容器不会进行排序。insert()插入函数；count()函数即当前值出现的次数。

1.遍历链表A，将链表A中的每个节点全部放入到容器中；

2.遍历链表B，判断B中当前节点是否在容器中；

• 如果当前节点不在容器中，即count() == 0；则继续遍历下一个链表；

• 如果当前节点在容器中，那么后面的节点都在该容器中，当前节点就是链表相交的第一个节点；

• 如果B中所有节点都不在容器中，那么说明A和B这两个链表不相交，返回null。

代码如下：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //实例化一个对象
        unordered_set<ListNode*> v;
        //先将链表中的节点都放到容器中
        ListNode* tmp = headA;
        while(tmp)
        {
            v.insert(tmp);
            tmp = tmp->next;
        }
        //然后再拿容器中的值和链表B中的节点比较，如果B中节点在容器中，那么后面的节点都在该容器中，当前节点就是链表相交的第一个节点
        tmp = headB;//代表链表B中当前节点
        while(tmp)
        {
            
            if(v.count(tmp))
            {
                return tmp;
            }
            tmp = tmp->next;
        }
        return nullptr;
    }
};

时间复杂度：O(M + N)；M是链表A的长度，N是链表B的长度。

空间复杂度：O(1)