Merge K sorted Linked List – Using Priority Queue

Objective: Given, K sorted linked list, Write an algorithm to merge all the linked list into one linked list which will be also be sorted.

Example:

List 1: -->1-->5
List 2: -->4-->8
List 3: -->4-->6-->9
List 4: -->2-->7-->10
Merged Linked List: 
-->1-->2-->4-->4-->5-->6-->7-->8-->9-->10

Approach: Use Priority Queue

Please read Priority Queue and Linked List if needed.

  1. Maintain a priority queue.
  2. Add the first node from all the lists into the priority queue.
  3. While the priority queue is not empty.
    1. Extract the node and add it to our result list.
    2. Add the next node (if present) from the extracted node list.
  4. Return the result list.

NOTE:

  • Override the Comparator so that priority queue will be sorted as per the Linked List Node value.

Please see the Code for better understanding

Complete Code:

Output:

-->1-->5
-->4-->8
-->4-->6-->9
-->2-->7-->10
Merged Linked List: 
-->1-->2-->4-->4-->5-->6-->7-->8-->9-->10

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: