题目描述（简单难度）

两个链表，如果有重合的部分，把相遇点返回。如果没有重合的部分，就返回。

思路分析

最暴力的方法就是选择链表 A 的每个节点，然后考虑链表 B 能否到达，但时间复杂度会达到 O(mn) 。

再进行优化的话，可以利用一个 HashMap，将链表 A 中所有的节点存入，然后遍历链表 B 的每一个节点，看 HashMap 中是否存在即可。时间复杂度优化到了 O(n)，但同时需要 O(n) 的空间。

接下来我们只考虑时间复杂度 O(n)，空间复杂度为 O(1) 的解法。

有一些（找出链表环的入口点）解法的影子。我们需要两个指针，分别从两个链表的某个位置开始遍历，当两个指针相遇的时候，刚好停在两个链表的相遇点问题也就解决了。

所以最关键的问题就是从链表的某个位置开始遍历，那么从哪个位置呢？

如果把问题简单化，假如两个链表有重合部分，并且两个链表的总长度相等。那么我们只需要让两个指针分别从链表头遍历即可，也就是下边的例子，指针 A 从 1 开始遍历，指针 B 从 4 同时遍历，那么两个指针就会在 7 相遇，就是我们要找的位置。

如果两个链表长度不相等呢，比如下边的例子。

为什么多走 2 步呢？很简单，因为没有重合的链表部分和 4 5 6 7 8，长度差了 2。怎么算出这个长度呢？我们只需要用两个链表的总长度做差即可（原因：重合部分相减为 0 ，最终结果就相当于不重合部分的差），也就是 8 - 6 = 2 。

综上，我们只需要算出两个链表的长度，让长的的链表提前走几步，然后再同时开始遍历，相遇点就是我们要找的位置。

这里看到另一种写法，但本质上和上边是一样的，分享一下。

上边的代码简洁了很多，它没有去分别求两个链表的长度，而是把所有的情况都合并了起来。

如果有重合部分，分两种情况。
- 长度相同的话， a 和 b 一定是同时到达相遇点，然后返回。
- 长度不同的话，较短的链表先到达结尾，然后指针转向较长的链表。此刻，较长的链表继续向末尾走，多走的距离刚好就是最开始介绍的解法，链表的长度差，走完之后指针转向较短的链表。然后继续走的话，相遇的位置就刚好是相遇点了。

综上，代码巧妙的把所有情况合并了起来。

最开始考虑这道题的时候，我还想了另一种思路。就是遍历某一个链表，把这个链表的每个节点进行标记，这里的话当然就是对 val 进行特殊标记。然后再遍历另一个链表，发现了这个标记也就找到了相遇点了。当然，这个标记一定得是可逆的，完成任务后我们要把原来链表的 val 进行还原。

-time-and-O(1)-memory-(72ms)) 看到了类似于标记的方法，蛮有意思，分享一下，分下边几步。

有了上边的几个数据就可以知道。

sumA == sumA2 的话，就表明两个链表没有重合部分。
sumA != sumA2 的话，sub = sumA2 - sumA，由于我们对重合部分的 val 进行了加 1，所以前后的差 sub 就刚好表示了重合节点的个数。同时我们知道链表 A 的总长度 lenA，所以我们只需要对链表 A 遍历 lenA - sub 次，就刚好会走到重合部分的开头了，也就是我们要找的相遇点。

代码如下。

上边算法的缺点就是，由于进行了加 1 操作，对于过大的数可能会引起溢出，此外求和也很有可能引起溢出。但思想还是很有趣的。

遇到题以后，可以对不同的情况分析，回想之前的一些思想，从而找到突破口。

添加好友一起进步~

如果觉得有帮助的话，可以点击这里给一个 star 哦 ^^