一 题目

求两个单向链表的最早公共交点；如果没有返回 null。

二 解析

链表是单向链表，即只有指向下一个节点的指针，而没有反向； 公共节点，指地址相同的节点。即假设链表 L1 中有一个节点 node1，L2 中有一个节点 node2，node1 = node2，注：这里的“=”，指的是 node1 和 node2 是同一个节点，也就是说，L1 和 L2 都持有了对一个节点的引用，那么就说两个节点实际上是一个公共节点。我们可以用下面的图来表示：

上图中的 node2 和 node3 就是公共节点，node2 是最早公共节点。

链表 L1 的长度 m，链表 L2 地长度为 n

三 算法设计

3.1 多次遍历

两个链表都是有限长度，最直接的方法，就是直接遍历。从链表 L1 的第一个节点开始，遍历 L2 的所有节点，判断 L1 的这个节点是否与 L2 中的某个节点是公共节点，如果是，则直接返回这个节点即可；如果遍历结束后发现没有找到，那么返回 nul.l。

时间复杂度：比较次数为 mxn，所以时间复杂度为 O(mxn)；

空间复杂度：只使用一个临时变量，空间复杂度为 O(1)。

3.2 倒序查找

上面的算法虽然能够找到公共节点，但显然效率太低。我们再看一下公共节点的定义，如果节点 node 是两个链表地公共节点，那么一定有 L1 从 node 之后，与 L2 的 node 之后节点完全相同。

基于这样的分析，我们从尾部向前查找就可以了，如果最后一个节点是公共节点，那么就继续向前查找，直到找到第一个公共节点。

但这里还有一个问题，因为给定的是两个单向链表，所以不能直接做倒序查找（前一个节点），所以我们需要处理一下。链表不可以，数组是可以的，所以思路为：

1、链表转数组，得到两个节点数组；

2、从两个数组的最后一个节点开始逐个向前比对，直到找到第一个公共节点位置。

示意如下：

时间复杂度：需要分别遍历一次链表，复杂度为 m+n，之后从尾部遍历查找一次，所以时间复杂度为 O(m+n+max(m, n))；

空间复杂度：需要使用两个数组存储节点，还有一个指针临时变量，空间复杂度为 O(m+n)。

3.3 首位对齐，指针逐个后移

再次分析，如果我们把两个链表按照尾部对齐，第一个公共节点一定出现在从后向前找的第 k 个节点，那么这个节点一定是链表 L1 的第 m-k 个节点，L2 的第 n-k 个节点。

也就是说，假设 m>n，那么我们直接从 L1 的第(m-n)个节点开始，与链表 L2 的第 1 个节点开始对比，如果相同，说明这个节点就是最早公共节点；如果不是，那么两个链表同时向后一位进行对比，判断是否是公共节点，如此下去。公共节点一定在我们比对的这些对节点之中。

这种方式下，如果两个链表的长度 m，n 是已知的，那么直接遍历就可以了，时间复杂度为 O(min(m, n))；

如果长度未知，那么我们需要遍历一次两个链表，得到两个链表地长度，然后再设置指针的起始位置并进行遍历，复杂度为 O(m+n+min(m, n))。

空间复杂度：因为只需要 m, n, 指针三个临时变量，所以空间复杂度为 O(1)。

四 总结

这是链表题中并不复杂的一道，如果在 leetcode 中，应该最多只属于中等难度。但从这道题中，我们仔细思考之后可以看出一些题目之外的东西。

做题的人看到的是完全相同的信息，但能给出的解答是不同的。也就是说，每个人对信息的理解、提取、利用的能力存在差异，导致会有部分人得不到最优的解答。算法题大多如此，同样的条件，充分利用之后，可以节约大量的时间或空间，这种思路，在工程中也未必不能适用。