Merge K Sorted Linked Lists
Published in
1 min readJan 20, 2017
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Sample Input:
1 -> 2
3 -> 4Sample Output:
1 -> 2 -> 3 -> 4
Solution:
Explanation:
I am using the priority queues which uses a binary heap to sort its elements based on the comparator. So the time complexity of this logic is O(n log k)
where k
is the number of input linked lists and n
is the total number of elements in the final linked list.