Union and Intersection of two Linked Lists

Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elements in output lists doesn't matter.
Example:
Input:
   List1: 10->15->4->20
   lsit2:  8->4->2->10
Output:
   Intersection List: 4->10
   Union List: 2->8->20->4->15->10
http://www.geeksforgeeks.org/union-and-intersection-of-two-linked-lists/

Intersection:  Using Hashset

But of course you can do much better.

Now, if you have a HashSet (or other near-O(1)) data structure available then this is what you can do:

Iterate over one list. Add each element to the set. Iterate over the second list. If the element is in the set then add it to the result list.

Solution: O(n)

Intersection of two sorted Lists:

http://www.geeksforgeeks.org/intersection-of-two-sorted-linked-lists/

List getIntersection(int[] a, int[] b){
    int apos = 0, bpos = 0
    List intersection
    while apos < a.length && bpos < b.length:
        if a[apos] == b[bpos]:
            intersection.add(a[apos])
            apos++, bpos++
        else:
            if a[apos] < b[bpos]:
                apos++
            else:
                bpos++
    return intersection 
}

Efficiency is O(m + n).