算法与数据结构（相交链表）

题目 思路 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; } };