How to find the intersection of two linked lists?

Question

like inputs-1 2 3 4
3 4 5 6
output-3 4
inputs-3 4 5 6
5 7 8 9
output-5

Answer 1

you could use a hash table

in python for example:
1) initialize a dictionary
2) go thru the first linked list and mark which elements you have encountered with 1 (if encountered same element twice in the first list, still initialize with 1)
3) go thru the second list but this time, if the value already exists, increment it
4) all values in the hash table with 2 or more are intersected

this will give complexity of 2n ~ O(n)

in java you also have HashMap object if i recall correctly (haven't write java in a while ._. )

https://beginnersbook.com/2013/12/hashmap-in-java-with-example/

https://www.tutorialspoint.com/java/java_hashmap_class.htm

Answer 2

you can create 2 array and for loop in for loop from 0 to array.size-1 and check if they are equal. for example :
int [] a = {1,2,3,4};
int [] b = {3,4,5,6};
for (int i=0; i<=a.size-1;i++){
for (int j=0; j<=b.size-1;j++){
if (a[i]==b[j])
System.out.print(b[j]+" ");
}
}.

or if your want to use intersection numbers you could put it in a empty array.
I hope that I help your.

Answer 3

but its complexity is n^2 and i want the compexity n or log n

Answer 4

this would be interesting as a challenge. The lists/arrays are sorted, right? This would be like trying to merge two sorted lists into another one (also sorted, of course) but instead of actually merging them, we only look for duplicates. I think this can be done in O(n). But idk java. In python, I think this would be even simpler with sets, since those don't allow duplicates. I'm sorry I don't have a concrete answer now though, I'm on my way to work :(