两个单链表只能存在Y型交叉,不会存在X型交叉。最简单的方式是直接遍历到两个链表的最后一个节点,判断它们是否相同。但这样做有两个问题,一是时间较长(尤其是链表很长的时候),其次是无法找到第一个交叉的点。应该如何改进呢?
判断最后一个节点是否相同的办法并不慢,如果两个链表长度m,n 那么复杂度O(m+n),这是最优的复杂度
第二个问题,如何寻找交叉节点:
指针p、q分别遍历链表a、b,假设q先到达NULL(即 假设a 比 b 长),此时从a的头发出一个指针t,当p到达NULL时,从b的头发出s,当s==t的时候即交点.