如何求n个单链表的交点？面试算法难题求助

先明确核心前提：单链表一旦相交，从交点开始往后的所有节点都是共享的，所以n个链表的公共交点是指所有链表都经过的某个节点，且该节点之后的所有节点在所有链表中完全一致。

为什么两两调用双链表交点方法会失效？ #

你之前的思路问题出在迭代逻辑上：如果只是单纯拿「原链表1和原链表2找交点，再拿原链表1和原链表3找交点」，得到的可能是两两之间的独立交点，而非所有链表的公共交点。正确的两两迭代应该是逐步缩小公共链范围：比如先找链表1和2的公共交点P，若不存在直接返回空；接着拿「从P开始的链」和链表3找公共交点（因为只有从P开始的部分才是1和2的公共部分，要找三个的公共，必须在这个范围内找）；以此类推，直到遍历完所有链表。但这个方法效率偏低，且链表数量多时代码冗余度高。

更高效的两种可行思路 #

思路一：哈希表统计节点出现次数 #

• 遍历所有链表的每个节点，用节点的内存地址（或唯一标识）作为key存入哈希表，每遇到一次该节点就将计数+1。
• 遍历哈希表，找到计数等于n（链表总数）的节点，这个节点就是所有链表的公共交点。
• 注意：如果没有这样的节点，说明不存在公共交点。
• 复杂度：时间O(M)（M是所有链表的总节点数），空间O(M)（最坏情况所有节点都不重复）。

思路二：长度对齐同步遍历（空间优化版） #

这个思路是双链表交点方法的扩展：

1. 计算每个链表的长度，记录最长链表的长度max_len。
2. 为每个链表设置一个指针，将所有指针先向后移动max_len - 当前链表长度步，让所有指针处于「距离各自链表尾端长度相同」的位置。
3. 同时移动所有指针，每次所有指针都向后走一步，检查所有指针是否指向同一个节点：
   • 如果是，这个节点就是公共交点；
   • 如果遍历到所有链表都走到尾端还没找到，说明不存在公共交点。

• 复杂度：时间O(M)，空间O(1)（仅用几个指针和长度变量）。

额外提示 #

不管用哪种方法，都要注意处理空链表的情况：如果有任意一个链表为空，直接返回空，因为空链表不可能和其他链表有公共交点。

内容的提问来源于stack exchange，提问作者cool