document.write('方法一：Hash法
如上图所示，如果两个链表相交，那么它们一定会有公共的结点，由于结点的地址或引用可以作为结
点的唯一标识，因此，可以通过判断两个链表中的结点是否有相同的地址或引用来判断链表是否相交。
具体可以采用如下方法实现：首先遍历链表head1，把遍历到的所有结点的地址存放到HashSet中；接
着遍历链表head2，每遍历到一个结点，就判断这个结点的地址在HashSet中是否存在，如果存在，那
么说明两个链表相交并且当前遍历到的结点就是它们的相交点，否则直接将链表head2遍历结束，说明
这两个单链表不相交。
算法性能分析：
由于这种方法需要分别遍历两个链表，因此，算法的时间复杂度为O(n1+n2)，其中，n1与n2分别为
两个链表的长度。此外，由于需要申请额外的存储空间来存储链表head1中结点的地址，因此，算法的
空间复杂度为O(n1)。
方法二：首尾相接法
主要思路：将这两个链表首尾相连(例如把链表head1尾结点链接到head2的头指针)，然后检测这个
链表是否存在环，如果存在，则两个链表相交，而环入口结点即为相交的结点，如下图所示。
方法三：尾结点法
主要思路：如果两个链表相交，那么两个链表从相交点到链表结束都是相同的结点，必然是Y字形(如
上图所示)，所以，判断两个链表的最后一个结点是不是相同即可。即先遍历一个链表，直到尾部，再
遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交，这时记下两个链表的长度n1、
n2，再遍历一次，长链表结点先出发前进|n1-n2|步，之后两个链表同时前进，每次一步，相遇的第一
点即为两个链表相交的第一个点。实现代码如下：
class LNode:
def __new__(self,x):
self.data=x
self.next=None
"""
方法功能: 判断两个链表是否相交, 如果相交找出交点
输入参数: head1与head2分别为两个链表的头结点
返回值: 如果不相交返回None, 如果相交返回相交结点
"""
def Islntersect(head1,head2):
if head1==None or head1.next==None or head2==None or\\
head2.next==None or head1==head2:
return None
temp1=head1.next
temp2=head2.next
n1,n2=0,0
# 遍历head1,找到尾结点,同时记录head1的长度
while temp1.next!=None:
temp1=temp1.next
n1+=1
# 遍历head2, 找到尾结点, 同时记录head2的长度
while temp2.next!=None:
temp2=temp2.next
n2+=1
#head1与head2是有相同的尾结点
if temp1==temp2:
#长链表先走|n1-n2|步
if n|＞n2:
while n1-n2＞0:
head1=head1.next
n1-=1
if n2＞n1:
while n2-n1＞0:
head2=head2.next
n2==1
#两个链表同时前进,找出相同的结点
while head1!=head2:
head1=head1.next
head2=head2.next
return head1
# head1与head2是没有相同的尾结点
else:
return None
if __name__="__main__":
i=1
#链表头结点
head1=LNode()
head1.next=None
#链表头结点
head2=LNode()
head2.next=None
tmp=None
cur=head1
p=None
#构造第1个链表
while i＜8:
tmp=LNode()
tmp.data=i
tmp.next=None
cur.next=tmp
cur=tmp
if(i==5):
p=tmp
i+=1
cur=head2
#构造第2个链表
i=1
while i＜5:
tmp=LNode()
tmp.data=i
tmp.next=None
cur.next=tmp
cur=tmp
i+=1
#使它们相交于结点5
cur.next=p
interNode=IsIntersect(head1,head2)
if interNode==None:
print "这两个链表不相交:"
else:
print "这两个链表相交点为:"+str(interNode.data)
程序的运行结果为：
这两个链表相交点为：5
运行结果分析：
在上述代码中，由于构造的两个单链表相交于结点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)。
');
![\"360截图20190815224114071.jpg\"](\"http://www.alatiku.com/d/file/shiti/72caa4ead3095d6cf7ce9b7221b54f26.jpg\")