算法与数据结构（相交链表）
题目
思路
1.哈希集合
因为要求是否存在相交节点，那么我们就可以利用哈希集合先将listA链表里面的所有数据存入，然后访问listB，判断其是否有节点在哈希集合中，若存在，则说明此节点为相交的节点。若遍历完之后仍没有发现，则说明两个表之间不存在相交节点，返回nullptr即可。
2.双指针
首先进行条件判断，若headA和headB中有一个为空，则说明不可能有相交节点，直接返回nullptr即可。
接着用cur1和cur2变量用来遍历listA和listB链表，循环中用了三元运算符，就第一个来说，若cur1为空，则直接将cur1赋值为headB,若不为空，则继续往下移动。
第二个也是如此，那为什么这样就可以求出它们的相交节点呢？
假设链表 headA 的长度为 m，链表 headB 的长度为 n，且它们的交点之后的公共部分长度为 k。
-
当
cur1遍历完headA后，它会开始遍历headB，此时cur1已经走了m步。 -
当
cur2遍历完headB后，它会开始遍历headA，此时cur2已经走了n步。 -
当
cur1和cur2都开始遍历对方的链表时，它们会在交点处相遇，因为此时cur1和cur2都走了m + n - k步。
如果两个链表没有交点，那么 cur1 和 cur2 最终都会指向 nullptr，此时返回 nullptr。
下面举个例子来看就容易理解了
listA: A1 -> A2 -> A3 -> C1 -> C2 -> C3
listB: B1 -> B2 -> C1 -> C2 -> C3
-
链表 listA 的长度为
m = 6。 -
链表 listB 的长度为
n = 5。 -
交点之后的公共部分长度为
k = 3（即C1 -> C2 -> C3）。
运行过程：
-
初始化指针：
-
cur1指向A1。 -
cur2指向B1。
-
-
遍历过程：
-
cur1依次遍历：A1 -> A2 -> A3 -> C1 -> C2 -> C3 -> nullptr。 -
当
cur1到达nullptr时，它已经走了m = 6步，然后切换到 listB，继续遍历：B1 -> B2 -> C1。 -
cur2依次遍历：B1 -> B2 -> C1 -> C2 -> C3 -> nullptr。 -
当
cur2到达nullptr时，它已经走了n = 5步，然后切换到 listA ，继续遍历：A1 -> A2 -> A3 -> C1。
-
-
相遇点：
-
当
cur1切换到 listB 后，它走了m + n - k = 6 + 5 - 3 = 8步。 -
当
cur2切换到 listA 后，它走了n + m - k = 5 + 6 - 3 = 8步。 -
两者会在交点
C1处相遇。
-
代码
1.哈希集合
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode*> s;while(headA){s.insert(headA);headA = headA->next;}while(headB){if(s.count(headB)){return headB;}headB = headB->next;}return nullptr;}
};2.双指针
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA == nullptr || headB == nullptr)return nullptr;ListNode* cur1 = headA;ListNode* cur2 = headB;while(cur1 != cur2){cur1 = cur1==nullptr ? headB : cur1->next;cur2 = cur2==nullptr ? headA : cur2->next;}return cur1;}
};