Sunday, July 19, 2015

intersection of two sorted lists

// a, b are sorted lists
intersection(a, b):
    if a == null || b == null:
        throw
    intersection = new
    ai = 0, bi = 0
    while ai < a.length && bi < b.length:
        if a[ai] == null:
            ai++
            continue
        if b[bi] == null:
            bi++
            continue
        c = a[ai].compare(b[bi])
        if c < 0:
            ai++
        else if c > 0:
            bi++
        else: // a[ai] == b[bi]
            intersection.add(a[ai])
            ai++
            bi++
    return intersection

No comments:

Post a Comment