me test series

Question

Given two unsorted singly-linked lists each with n distinct elements. There exists an efficient intersection algorithm, that computes and returns a new list with common elements between the input lists. How much time does the intersection algorithm requires in worst case, if it is allowed to use constant extra space only?

answer is qiven as O(nlogn)...........i think it should be O(n^2)...please verify

Comments

which algo will u prefer it so it can be sorted in nlogn times

---

ok i got merge sor + merge sort +merge ???

---

yes right :D

Answer 1

a) The two lists can be sorted first by .. let's say merge sort -> O(nlogn)

b) if the two sorted lists are L1, L2 then,

 

for element in L1:                    # will run for n times

{    Binary_search(L2, element)  # O(logn), will return the matched element.

   if matched:

       insert_into(L3)                    # O(1)

}

 

 

Total Time = a) + b) = O(nlogn) + O(n*(logn + 1)) = O(nlogn)

Comments

how you are applying binary search on linked list in O(log n)

---

Oh yes. Shoot !

My bad.