如何判断两个链表是否相交，假设两个链表都没有环？

首先，很多同学会存在一个误区，认为两个链表相交应该这样的。

如果把它用结点的形式来表示就这样的。

很显然，相交的这个结点的next指针既指向了这个这个结点，又指向了这个结点，明显不科学。

真正相交的链表，应该是这样的。

如果两个链表相交，那么一定有重合的结点，所以可以逐个判断第一个链表里面的结点是否在第二个链表中，这种办法可行，就是效率太低，放在笔试题中往往时间复杂度满足不了。

我们稍微分析一下就会发现，相交的两个链表，他们的最后一个结点一定是重合的。

所以只要让第一个链表的指针指向最后一个结点，第二个链表的指针也指向最后一个结点，判断这两个结点是否相同，就能解决问题。

这个时候，往往面试官会接着问，如何找出相交的那个结点。

刚才的方法只适用于判断是否相交，如果想找出相交的结点，好像不太容易。

我们得换个方法，既能判断是否相交，又能找出相交的那个结点。

如果两个链表的长度一样，只要同时移动指针，最先相等的那个结点一定就是相交的结点。

所以可以先计算两个链表的长度差，然后先移动一个指针，保证长度一样后，再同时向后走。代码也没什么难度，直接附上。

审核编辑：刘清

查看全文

作者最近更新