java - 在两个排序列表中查找匹配项比使用 for 循环更好的方法？

Question

我有两个排序列表，都按非递减顺序排列。例如，我有一个包含元素 [2,3,4,5,6,7...] 的排序链表，另一个包含元素 [5,6,7, 8,9...]。

我需要在两个列表中找到所有公共(public)元素。我知道我可以使用 for 循环和嵌套循环来迭代所有匹配项以找到相同的两个元素。但是，有没有另一种运行时间小于 O(n^2) 的方法？

Answer 1

您可以在 O(n) 时间内完成。伪代码:

a = list1.first
b = list2.first
repeat:
    if a == b:
        output a
        a = list1.next
        b = list2.next
    elif a < b:
        a = list1.next
    else
        b = list2.next
until either list has no more elements