输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 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) 内存。
本题与主站 160 题相同：https://leetcode-来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一开始是认为两个链表重合的话，那么它们的链表尾一定会是相同的，于是想采用两个栈将两个链表中的结点分别压入两个栈汇中，然后同时从两个栈中取出数据，找到两个栈中最后一次取出的相同的数据就是我们的返回结果。
但是这道题官方的测试用例中的链表可能是从头重合，然后尾部不重合的。
官方的测试用例中有A链表为3->2，B链表为3的。
所以我们采用下面这个，用一个map来记录A链表中的所有结点是否被访问过，然后再遍历B中的所有结点，看B中的结点A中是否也有。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
map<ListNode*,int> record;
ListNode* temp=headA;
while(temp!=nullptr)
{
record[temp]=1;
temp=temp->next;
}
temp=headB;
while(temp!=nullptr)
{
if(record[temp])
{
return temp;
}
temp=temp->next;
}
return nullptr;
}
};
但是上面这种算法太慢了，我们可以使用下面这种双圈指针法
[4,1,8,4,5]
[5,0,1,8,4,5]
对于上面两个链表，我们可以使用两根指针p1,p2同时从A链表和B链表从前向后遍历，如果p1先走到头了，也就是我们的p1==nullptr，就将我们的p1指向B链表的头结点
如果我们的p2走到头了，也就是p2==nullptr，就将我们的p2指向A链表的头结点
p1: 4->1->8->4->5->5->0->1->8->4->5
p2: 5->0->1->8->4->5->4->1->8->4->5
从上面的遍历结果我们发现从标红的位置开始，我们的两个指针指向的结点重合了，所以我们判断跳出的条件就是p1指针和p2指针指向的结点是一样的。
为什么会发生这种情况？
因为我们原本链表因为长度不同，所以在遍历的过程中我们的两个结点并不能同时到达相交的结点，但是这种方法让我们的链表A和B连接了起来，也就是我们的p1和p2所走过的结点数量是相同的，并最终能够同时到达最终的结点。
A [4,1,8,4,5]
B [5,0,1,8,4,5]
这里我们观察到A链表前面的[4]和B链表前面的[5,0]长度是不同的，那么怎么才能让我们链表同时走到相同的部分呢？就是让p1走完A链表之后，再走B链表前面的[5,0]，让p2走完B链表之后，再走A链表前面的[4]，也就是说，我们的p1,p2其实都会将[4]和[5,0]部分遍历一遍，最终就同时到达了重合的链表的位置。
如果两条链表不重合怎么办？
A [4,1,2,3,8]
B [5,0]
上面两根链表是不重合的，但是我们上述的算法依然有效。也就是p1，先遍历一遍A，再从B链表的头结点遍历一遍B
我们的p2先遍历一遍B再从A链表的头结点开始遍历一遍A。
也就是说我们的p1和p2都会将A,B链表遍历一遍，并且同时到达A,B链表的结尾，也就是nullptr，并随着p1==p2的跳出条件，将nullptr返回。
// /**
// * Definition for singly-linked list.
// * struct ListNode {
// * int val;
// * ListNode *next;
// * ListNode(int x) : val(x), next(NULL) {}
// * };
// */
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1=headA;
ListNode *p2=headB;
while(p1!=p2)
{
if(p1!=nullptr)
{
p1=p1->next;
}
else
{
p1=headB;
}
if(p2!=nullptr)
{
p2=p2->next;
}
else
{
p2=headA;
}
}
return p1;
}
};