1.11 如何判断两个单链表（无环）是否交叉

难度系数：★★★★☆

被考查系数：★★★★★

题目描述：

单链表相交指的是两个链表存在完全重合的部分，如下图所示：

在上图中，这两个链表相交于结点5，要求判断两个链表是否相交，如果相交，找出相交处的结点。

分析与解答：

方法一：Hash法

如上图所示，如果两个链表相交，那么它们一定会有公共的结点，由于结点的地址或引用可以作为结点的唯一标识，因此，可以通过判断两个链表中的结点是否有相同的地址或引用来判断链表是否相交。具体可以采用如下方法实现：首先遍历链表head1，把遍历到的所有结点的地址存放到HashSet中；接着遍历链表head2，每遍历到一个结点，就判断这个结点的地址在HashSet中是否存在，如果存在，那么说明两个链表相交并且当前遍历到的结点就是它们的相交点，否则直到链表head2遍历结束，说明这两个单链表不相交。

算法性能分析：

由于这种方法需要分别遍历两个链表，因此，算法的时间复杂度为O(n1+n2)，其中，n1与n2分别为两个链表的长度。此外，由于需要申请额外的存储空间来存储链表head1中结点的地址，因此，算法的空间复杂度为O(n1)。

方法二：首尾相接法

主要思路：将这两个链表首尾相连（例如把链表head1尾结点链接到head2的头指针），然后检测这个链表是否存在环，如果存在，则两个链表相交，而环入口结点即为相交的结点，如下图所示。具体实现方法以及算法性能分析见1.6节。

方法三：尾结点法

主要思路：如果两个链表相交，那么两个链表从相交点到链表结束都是相同的结点，必然是Y字形（如上图所示），所以，判断两个链表的最后一个结点是不是相同即可。即先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交，这时记下两个链表的长度n1、n2，再遍历一次，长链表结点先出发前进|n1-n2|步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。实现代码如下：

程序运行结果为

运行结果分析：

在上述代码中，由于构造的两个单链表相交于结点5，因此，输出结果中它们的相交结点为5。

算法性能分析：

假设这两个链表长度分别为n1和n2，重叠的结点的个数为L(0<L<min(n1，n2))，则总共对链表进行遍历的次数为n1+n2+L+n1-L+n2-L=2(n1+n2)-L，因此，算法的时间复杂度为O(n1+n2)；由于这种方法只使用了常数个额外指针变量，因此，空间复杂度为O(1)。

引申：如果单链表有环，如何判断两个链表是否相交？

分析与解答：

（1）如果一个单链表有环，另外一个没环，那么它们肯定不相交。

（2）如果两个单链表都有环并且相交，那么这两个链表一定共享这个环。判断两个有环的链表是否相交的方法为：首先采用本章第1.6节中介绍的方法找到链表head1中环的入口点p1，然后遍历链表head2，判断链表中是否包含结点p1，如果包含，则这两个链表相交，否则不相交。找相交点的方法为：把结点p1看作两个链表的尾结点，这样就可以把问题转换为求两个无环链表相交点的问题，可以采用本节介绍的求相交点的方法来解决这个问题。