Merging sorted arrays stored as linked lists

Question

I have $k$ sorted arrays stored as linked lists. I need an algorithm to merge them into one single sorted array, also stored as a linked list. How can I do that?

My Code:

Function merge(A[k]) 
Begin:

// A is array of list to merge.
Array result;
temp //array to save element in each list 
For (i=0:i<k:i++):
Temp.add(A[i].head.value);

While(result.size<n):
 Minvalue, index = temp.pop()
 Result.add(minvalue)
 Value = 0
 If( A[index].head.next==Null):
   Value = maxInt 
 Else :
  A[index].head = A[index].head.next
  Value = A[index].head.key Temp.add(value)
 Return result;
 
End

Answer 1

When $k = 2$, you can use the classical merge routine of Merge Sort, which fits the linked list data structure well. In this routine, you repeatedly compare the smallest elements of both arrays, adding the smaller one to the new array, and removing it from its own array.

You can use the same idea for general $k$. Instead of comparing the $k$ smallest elements at every step, you can use a priority queue that stores the smallest elements of each array, thus improving the running time of every step from $\Theta(k)$ to $O(\log k)$.