Better way to find matches in two sorted lists than using for loops?

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

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

Answer 2

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)