This page explains Java solution to problem Merge K Sorted Lists
using Priority Queue
data structure.
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.
Example 1:Example 2:Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Input: lists = [[]]
Output: []
package com.vc.hard;
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class MergeKSortedLists {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>(){
public int compare(ListNode l1, ListNode l2) {
return Integer.compare(l1.val, l2.val);
}
});
for(ListNode list: lists) {
if(list != null)
pq.offer(list);
}
ListNode dummy = new ListNode(-1);
ListNode head = dummy;
while(!pq.isEmpty()) {
ListNode node = pq.poll();
dummy.next = node;
dummy = dummy.next;
if(node.next != null)
pq.offer(node.next);
}
return head.next;
}
}
O(N * log(K))
Where N is total number of elements in the final list and K is number of input lists.
O(K) Where K is number of input lists.