如何高效地判断两个单链表是否有交叉？

两个单链表只能存在Y型交叉，不会存在X型交叉。最简单的方式是直接遍历到两个链表的最后一个节点，判断它们是否相同。但这样做有两个问题，一是时间较长（尤其是链表很长的时候），其次是无法找到第一个交叉的点。应该如何改进呢？

判断最后一个节点是否相同的办法并不慢，如果两个链表长度m,n 那么复杂度O(m+n)，这是最优的复杂度

第二个问题，如何寻找交叉节点:

指针p、q分别遍历链表a、b，假设q先到达NULL（即 假设a 比 b 长），此时从a的头发出一个指针t,当p到达NULL时,从b的头发出s,当s==t的时候即交点.