Suppose we maintain two linked lists of length n in sorted order.What would be the big-Oh notation for the creating a third list, which included only elements common to both lists? A)O(1) B)O(n) C)O(n log n) D)O(n²)

Question

Quizplus · Accepted Answer

We can traverse both the linked lists simultaneously and compare each element. If the elements are same, we add it to the third list. This operation takes linear time, O(n), since we need to traverse both the linked lists once. Therefore, the overall time complexity of creating a third list with common elements is O(n).

Suppose We Maintain Two Linked Lists of Length N in Sorted