看动画，拿 Offer：大厂算法面试真题全解析( 四 ) _链表

另外，本题有多种解法。实现算法时，应尽量使算法的时间复杂度为 O(n) ，空间复杂度为 O(1)。
来看一个例子，链表 A 为 4、1、8、4、5 ，链表 B 为 5、0、1、8、4、6 。两个链表此时相交于值为 8 的节点，我们应将该节点的地址返回。
题目中节点的数据结构，代表链表中的一个节点， val 是节点中存储的数据， next 是指向下一个节点的指针，构造函数初始化 val 的值为 x ， next 赋为空。
我们需要开发求两个链表，交点的函数，函数传入两个链表的头结点指针 headA 与 headB 。如果两个链表有交点，函数返回相交节点的地址，否则返回 NULL 。
我们来分析一下这个题目。
首先可以想到两层循环来直接求解该问题，用 headA 遍历链表 A ，对 A 中的每一个节点使用 headB 遍历 B 中的每个节点，并同时检查 headB 是否与 headA 相同。如果相同，说明找到了两个链表的交点。
例如，最初 headA 指向 A 的第一个节点，通过 headB 遍历 B 中的节点时并没有发现地址与 headA 相同的节点。然后我们向后移动 headA ，在链表 B 中，同样没有找到地址相同的节点。
当 headA 指向第 3 个节点时，使用 headB 遍历链表 B 中的节点找到了与 headA 地址相同节点即两链表的交点，此时将它返回即可。
如果两个链表没有交点，最终 headA 于 headB 均会指向 NULL ，程序返回 NULL 。
假设链表 A、B 长度为 n ，该方法的时间复杂度为 O(n^2) ，并不是理想的方法。
我们再介绍两个更优的算法。
第一种方法，通过 STL 中的 set 来优化搜索相同地址的过程。
首先构建一个空的 set 。然后遍历链表 A ，将 A 中每个节点的地址插入到 set 中。例如将地址 0x00A、0x00B、0x00C 等，添加至 set 再遍历链表 B ，将 B 中每个节点的地址在 set 中进行查询。当遇到第一个 set 中已出现的地址时，即找到了两个链表的交点，否则两个链表没有交点。
例如遍历至节点 8 时，发现它的地址 0x00C 已经在 set 中出现，那么该节点为两个链表的交点，我们将它的地址返回。如果遍历了链表 B 中的全部节点，没有找到在 set 中出现过的地址，则说明链表中没有环。
在正式讲解题目代码之前，我们先看一下 set 容器的使用。
样例代码利用 STL set 找出数组 a 与 b 中同时出现的元素，首先需要# 引用 set 类的头文件。在 main 函数中，创建命名为的 set 和数组 a、b 。首先遍历数组 a ，将 a 中的元素添加至，然后遍历数组 b ，检查 b 中的元素是否在中出现。如果中出现过该元素，则将它打印至屏幕，最终我们得到 a 与 b 中同时出现的元素为 5、1、8、4、5 。
然后我们来讲解该方法的代码实现。
首先，设置用来判断相同节点的集合，指针存储两链表的交点，初始化为 NULL 。使用 while 循环遍历链表 A 将链表 A 中的节点地址添加至，然后遍历链表 B ，通过代码 .find(headB) != .end()判断节点是否在中出现。如果 if 条件成立，说明找到了重复的节点，而第一个重复的节点即为链表相交的交点将它存储至，跳出循环，最终函数返回。