查找两个有重复项的链表的交集

Question

假设我有两个链表6->14->45->38->52->18->90->null和78->38->44->6->85->52

这里，第二个链表在节点52处与第一个链表连接，并且元素38和6也存在于两个列表中。获取这两个链表与元素52的交点的最佳方法是什么？

Answer 1

查找两个链表l1和l2的交集的一种简单有效的方法是散列。以下是您可以使用的方法：

通过h.

• Go将所有节点的地址插入到h.

• Go中，

1. 生成一个空的哈希表h，其中键是节点的地址，值是指示节点是否存在于l1中的二进制/布尔值。对于每个节点，检查它是否存在于h中。如果我们在h中找到一个节点，则该节点与l1和l2相交。

该算法对h具有O(m + n)时间复杂度和O(m)额外辅助空间，其中m为l1的大小，n为l2的大小。