One solution (for performance) would be to use a SortedSet like so
public static List<Integer> intersection2(List<Integer> a, List<Integer> b) {
SortedSet<Integer> aSet = new TreeSet<Integer>(a);
aSet.retainAll(b);
return new ArrayList<Integer>(aSet);
}
Another solution (for space) would be use the passed in List(s) like so (EDITED with the "new requirement" that the passed in List(s) be unchanged),
public static List<Integer> intersection3(List<Integer> a, List<Integer> b) {
List<Integer> c = new ArrayList<Integer>(a); // <-- new requirement.
c.retainAll(b);
return c;
}