My confusion with these kinds of problems is whether or not a whole new Linked List must be created.

The first time I solved this problem, I used a modified approach to the merge 2 sorted lists problem.

The second time I solved this problem, priority queue came to my mind because the lists are already sorted.

What mistakes did I make?

- I inserted all the nodes in all the lists in to the priority queue. This is not needed. The size of the priority queue should be at most
`k`

for an optimal solution. - I did not check the input for
`NULL`

before inserting nodes in to the priority queue.

The time complexity is `O(N log(k))`

where `N`

is the total number of nodes and `k`

is the number of Linked Lists. Inserting and removing from the priority queue is a `log(k)`

operation which is done `N`

times.

The space complexity is `O(N + k)`

or `O(N)`

if `k`

is much smaller than `N`

.

The problem is taken from Leetcode.

Solution is hosted on Github.