天天看点

两个单链表判断是否相交

本题看似简单,但其实暗藏玄机,有篇博客对这个问题讲的很详细,且分析了很多种方法,我也不打算再重复造轮子了,我这里就算是对他的一个精简版。

开篇借他的一张图:

两个单链表判断是否相交

或许我们看到这个题目的时候,马上就能想到这张图,并且以为很简单,因为只要是相交,最后一个节点一定是相同的,只要将两个单链表都遍历到最后一个元素,看看是不是相同就行了。

如果这道题真的这么简单那也没必要单独拎出来讲了,它其实是比较难的一道题,难就难在它的相交,可以是上面那样的相交,但也可以是带环的相交!

再借一张图

两个单链表判断是否相交

喏,这下咱根本遍历不到链表尾了,咋办?

这下这道题就变成了另外一道题了,即:如果单链表有环,如何找到这个环的入口!

继续阅读