Linked list time complexity

Question

Given two singly linked list of size n. The time complexity of computing the union and intersection of two linked list is.

a) O(n) and O(nlogn)

b) O(n) and O(n)

c) O(nlogn) and O(nlogn)

d) O(nlogn) and O(n)

Comments

in that case the correct answer should be O(mlogm + nlogn) rt???

---

in this question what is m?

---

sorry I got it  m=n  O(2nlogn) = O(nlogn)

Answer 1

Should be O(n).

For union :

Take all elements of the first list and simultaneously construct a hashtable for first list. This takes O(n) time.

For 2nd list, probe elements in the hash table first. If there is collision, don't put it in the union list, else put it. This takes O(n) time. Hence net time : O(n).

For intersection :

Construct hastable for first list. This will take O(n) time.

For 2nd list, probe elements in the hash table first. If collision happens, put it in intersection list. This also takes O(n) time. Hence net time : O(n)