Better way to find matches in two sorted lists tha

Question

I have two sorted lists, both in non-decreasing order. For example, I have one sorted linked list with elements [2,3,4,5,6,7...] and the other one with elements [5,6,7,8,9...].

I need to find all common elements in both lists. I know I can use a for loop and a nested loop to iterate all matches to find the same two elements. However, is there another way to do this that has running time less than O(n^2)?

Answer 1

Convert the first list to a HashSet; then iterate through the second list checking whether each element is in the HashSet.

Answer 2

In the main loop, take the first elements from both lists and compare. If they are not equal, scan the list with less element until it gets equal or more than the element of the other loop. If it gets equal, this means you found a common element. Read both list sequentially until the common element is passed. Continue the main loop. The complexity of this approach is O(n+m).

Answer 3

Actually you can do a little better:

def dropWhile(ls, cond):
    if cond(ls[0]): return dropWhile(ls[1:], cond)
    return ls

def bisect(ls, v):
    """
    Finds largest i s.t. ls[i]<=v and returns it.
    If no such i exists it returns -1.
    Runs in O(log n)
    """
    pass

def find_commons(ls1, ls2, ret):
    if not (ls1 or ls2): return
    i = bisect(ls2, ls1[0])
    if i<0: find_commons(ls2, ls1[1:], ret)
    elif ls2[i]==ls1[0]:
        ret.append(ls1[0])
        trim = lambda ls: dropWhile(lambda x: x==ls1[0], ls)
        find_commons(trim(ls1), trim(ls2), ret)
    else: find_commons(ls2[i+1:], ls1, ret)

Answer 4

You can do it in O(n) time. Pseudocode:

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