🚀 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。
🚁 个人主页：不 良
🔥 系列专栏：🛸剑指 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)文章来源地址https://www.toymoban.com/news/detail-495655.html
思路二：
哈希集合。
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的长度。文章来源：https://www.toymoban.com/news/detail-495655.html空间复杂度：
O(1)
到了这里，关于剑指 Offer 52. 两个链表的第一个公共节点的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
