Tag Archives: 无环

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

编程之美上的一道题。

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

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

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

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

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

代码如下[......]

继续阅读