Question

求链表的相交节点

Answer 1

下图中左图为无环链表，右图为有环链表

方法一 ：将节点一个一个放入 HashSet 中，在放入之前判断 HashSet 之中是否有当前节点，如果有，则是有环链表，当前节点就是入环节点；如果到 null 值还没有就是无环链表。

方法二 ：快慢指针。快慢指针都从头节点出发，快指针一次走两步，慢指针一次走一步，如果链表无环，那么快指针一定会走到 null；如果链表有环，那么快慢指针总会相遇，当快慢指针相遇时，我们令快指针指向链表头节点，然后快慢指针都一次走一步，快慢指针再次相遇时的节点，就是该有环链表的入环节点。

链表相交有两种情况，有环链表和有环链表相交，无环链表和无环链表相交，有环链表和无环链表不可能相交。

无环链表相交后，从相交节点开始一直到 null 的所有节点都是二者公共节点，因为一个节点的 next 只能指向一个节点。

大概思想是首先遍历两个链表，获取到它们的长度，计算长度差 n， 由于两个链表后面部分是相同的，所以要想求相交节点，需要先遍历较长链表的 n 个节点，然后长链表的第 n+1 个节点与短链表的第 1 个节点开始比较，直到两个链表某个位置上的节点相等，该节点就是相交节点。

有环链表相交有两种情况，如下图所示

判断属于哪种相交只要利用上面判断是否是有环链表的方法，分别求出两个有环链表的入环节点，如果两个入环节点相同，属于环外相交；如果入环节点不同，则属于环内相交。

环外相交求相交节点与无环链表求相交节点类似，唯一的区别是，无环链表的终止节点是 null，而环外相交的终止节点是入环节点。

环内相交要从第一个链的入环节点开始遍历，如果某个节点与第二个链表的入环节点相同，那么证明是环内相交，返回两个链表的任意一个入环节点都是相交节点。

运行结果：