[Leetcode] Merge k Sorted Lists

Problem

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Algorithm

Assume there are k lists, and each has a length of n. 

1. Brute Force

Merge lists one by one.  T(k,n) = T(k-1,n) + O(k*n) = O(k^2*n). 

2. Divide-and-Conquer

Divide the lists into two halves, and recursively merge two sublists. Then merge two merged lists. 

T(k, n) = 2T(k/2, n) + O(k*n) = O(k*log(k)*n).  

3. Priority Queue

Maintain a priority queue of size k, which are composed of all the smallest elements of k lists. Build the result by removing the smallest element from the queue, and add next element from that array. Since each operation of the priority queue needs O(log(k)) time, and there are O(k*n) elements in total. The running time is O(k*log(k)*n).

Code