This post is completed by 1 user

  • 0
 Add to List
Hard

359. 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

Output:

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

Related Problems: