optimization - 找到两个链表与重复项的交集

Question

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

这里第二个链表在节点 52 处与第一个链表连接，并且元素 38 和 6 都出现在两个链表中。在此处节点与元素 52 之间获取这两个链表交点的最佳方法是什么。

Answer 1

找到两个链表交集的一种直接/有效的方法，l1和 l2 , 正在散列。您可以使用以下方法:

1. 制作一个空哈希表h ，其中键是节点的地址，值是二进制/ bool 值，指示节点是否存在于 h 中。 .
2. 通过l1并将所有节点的地址插入 h .
3. 通过l2 .对于每个节点，检查它是否存在于 h 中.如果我们在 h 中找到一个节点，则此节点与 l1 相交和 l2 .

这个算法有O(m + n)时间复杂度和 O(m) h 的额外辅助空间, 其中m是 l1 的大小, 和 n是 l2 的大小.