文章目录

1. 1. Intersection Of Two Linked Lists

Intersection Of Two Linked Lists

---

问题是求两个链表是否相交，如果相交，求出它们相交的第一个节点。这个链表是无环链表。

首先我们需要知道如果两个链表相交的话，那么他们剩下的节点都是相同的。

这个题目最简单的方法当然是O(mn)复杂度的方法，就是两个链表中的节点相互比较。

第二个方法是用hash的方法来记录一个链表的内存地址，用遍历另一个链表来判断是否出现在hash中。这个方法的时间复杂度是O(m+n)，但空间复杂度是O(n)。

我的方法是应用我们上面讲的事实，用两个链表的最后一个元素进行比较，如果不同，说明它们之前并没有相交过；如果相同，那么需要返回第一个相交的节点。我们在获取最后一个元素的时候可以获取整个链表的长度，接着将更长的链表向前访问两个链表长度之差个。找到它们最先相同的节点即可。比如

链表B需要从b2开始访问。