Scala Programming

Question:

Write a function unionOfLists that inputs two lists of integers (sorted in ascending order) and returns a list of integers. The function must compute the union of the two input lists to return a list that is also sorted in ascending order. Note that in performing the union, each number can appear at most once in the output list.

Example Input lists List(1, 3, 4, 6), and List(2, 3, 4, 5), the output should be List(1, 2, 3, 4, 5, 6)

Input lists List(1, 2, 3, 4) and List(1, 2, 3, 5), the output should be List(1, 2, 3, 4, 5)

Restrictions Suppose the lists are of size 1n1 and 2n2, respectively, the entire algorithm must run in linear time: (1+2)O(n1+n2). Please do not use inbuilt sort algorithms (they would take ((1+2)log(1+2))O((n1+n2)log(n1+n2)) time. Also note that when you append one list to another using ++ operator or an element to the end of a list using :+ operator inside a loop, the result may actually violate the linear time complexity restriction.