Buenas,
En mi opinión la idea detrás de este código cumple con los requisitos que pide el ejercicio, pero tome algunos supuestos que no se si esta bien hacerlos.
Supuse que tenía los largos de las listas porque sino, no se me ocurría otra manera mas que recorrerlas para saberlos y ahí el tiempo sería O(2n+2m).
También asumí que tenía una buena función de Hash y como largo del hash usé el mínimo del largo de las dos listas, pero no se si es una buena elección.
Respecto al código, utilicé para las listas las operaciones de el ej 4 sobre lista de puntos y para Thash las asumí implementadas.
Gracias.
ListaEnt interseccion(ListaEnt A,largoA,ListaEnt b,LargoB){
int largoT=min(largoA,LargoB);
Tabla Thash=crearTabla(largoT);
Tabla res=crearLista();
for(int i=0;i<largoA,i++){
agregarT(primero(A),Thash);
A=resto(A);
}
for(int i=0;i<LargoB;Thash){
if(perteneceT(primero(b),Thash)
cons(primero(b),res);
B=resto(B);
}
return res;
}