N linkedlists of K elements each....

Question :

Let us say there are N linked lists of K elements each. Each of the linked lists are sorted. Then give an algorithm to merge N linked lists to form another sorted linked list.

Solution 1 :

Take the first element of each linked list and create a sorted linkedlist of these elements. Call it X. Each element of X would contain a ( ptr, value ) pair. And X would be sorted by value.

Let the first element of X be A.

A ('s value) would be the first element of the result list Y. Find the next element from the list to which A belongs. and insert that element into the list X at appropriate location. ( insert it such that X would be still sorted).

Now the first element of X would be second element of result list Y. and the same process can be repeated for NK times to get the result list Y.

Time complexity : Time complexity to create X + Time complexity of the rest operations.

= O ( N * log(N) ) + (N*K) * O (N) [ Time complexity to insert an element into a sorted linked list is O(N) ]

= ( N*K ) * O (N)

Space complexity : Need another linked list of size N

Solution 2 :

Similar to the above sln.. but to use an additional heap instead of the linkedlist. Create a heap of (size N) first elements from all the lists - X . Pop the smallest element ( let's say A ) from the heap. and that would be the first element of the result list. Find the next element of the list from which A came. and insert it into the heap. For each element inserted into heap it takes O(log N) time.

So, Time complexity = Create a heap + rest operations

= O(N) + ( N*K ) * O (log N)

= O ( (N*K) * (log N) )

Space Compexity: A heap of size N

Using the right data structure is the key..