判断链表是否相交(无环版)

编程之美上的一道题。

给出两个单向链表的头指针,比如h1和h2,判断这两个链表是否相交。先假设链表不带环。

首先对于“链表相交”这个概念,要澄清一下,不是单点相交,而是如下这种:

其实也很好理解,相交在平面几何里面的概念是点重合。那么对于链表中某个结点重合,必然next指针也是一样的,于是就是上面这个样子了。

思路:如上分析后就很简单了,如果相交,那么肯定从h1找到尾部(NULL的前一个)和好

找到的尾部是重合的。如果不重合,肯定不相交,是重要条件。

代码如下:

其他支持代码如下:

 如果现在要求把重复的部分打出来应该怎么做呢?

其实也不复杂,我们设A链表A和B的长度分别是是L(a)和L(b),则让短的哪个链表走 |L(a) – L(b)| 步,然后开始比较两个指针,直到有相等的即可。

代码如下:

Leave a Reply

Your email address will not be published.