访谈:从两个链接列表中找到相似的元素，并将结果作为链接列表返回

Question

这个问题是在对我朋友的采访中提出的。面试官要求找出算法并用Java编写代码

问题:从两个链接列表中查找相似的元素，并以链接列表的形式返回结果

例:如果linkedlist1有1->2->3->4->4->5->6，而linkedlist2有1->3->6->4->2->8

结果链接列表1->2->3->4->6

谢谢

Answer 1

不如：

return new LinkedList(new LinkedHashSet(list1).retainAll(list2));

这将保留订单，如list1中的那样。当然，有人可能会抱怨这是欺骗，如果发问者意味着你应该自己构建算法，但是如果唯一的限制是“用Java编写代码”，那么这是一个有效的解决方案(而且很可能比任何人手工制作的低级解决方案更高效、更无错误)。

Answer 2

创建一个哈希表。

通过第一个链接列表，在访问时标记条目。O(N)通过第二个链接列表，标记条目(不同的标志等)，当你访问他们。O(男性)

遍历哈希表并查找所有包含两个LL成员的条目。在找到条目时创建新的LL成员。O(H)

总复杂度: O(N)+ O(M) + O(Max(N，H，M)) => O(N)

注: Saurabh编辑的答案。

Answer 3

获取第一个链接列表并从第一个元素开始，将其与第二个链接列表的第一个元素进行比较，如果它们相同，将值添加到结果，然后转到第一个列表的第二个元素，否则转到第二个列表的第二个元素，这样做直到值相同或到达第二个列表的和。