如何在两个链表中查找最新的等元素？

有两个linked lists。他们有共同的尾巴。我想找到最新的元素，这两个列表中都是相同的。如何在两个链表中查找最新的等元素？

例如，

List1是10-> 4-> 5-> - > - > 53-> 64> 345-> 23

List2是10- > 4-> 5-> - > - > 53-> 64> 345-> 23-> 43-> 53

我想找到2.

我们可以遍历O(n)中的列表。

有没有更好的方法来找到需要的元素，比在O(min(n, m))？

来源

2015-03-02 Denis

遍历一个链表的唯一方法是O（n），所以我看不出有任何的算法为O更好的工作（N + M）。 – Phylogenesis 2015-03-02 14:26:46

'O（n + m）'是一个明显的答案。我希望，有更好的解决方案... – Denis 2015-03-02 14:27:45

那么，我想严格的答案是O（min（m，n））为最明显的算法。 – Phylogenesis 2015-03-02 14:28:45

node1 = list1head 
node2 = list2head 
ans = {error} 
while(node1 && node2 && node1.data == node2.data) 
    ans = node1.data 
    node1 = node1.next 
    node2 = node2.next 
end while 
return ans

Cost = O(min(m, n))

来源

2015-03-02 14:28:51

谢谢你的回答。这是一个正确的解决方案，但是我希望，这个算法可能存在一些更好的东西。 – Denis 2015-03-02 14:32:31

对于单向链表，你不能以比这更快的速度来遍历。 – 2015-03-02 14:33:06

如何在两个链表中查找最新的等元素？

回答

相关问题