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

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

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

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

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

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容