Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
//time complexity O(nlogk), where n is the number of ListNodes and k is the lists size)
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
Queue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode a, ListNode b) {
return Integer.compare(a.val, b.val);
}
});
for (ListNode listNode : lists) {
if (listNode != null) {
pq.offer(listNode);
}
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!pq.isEmpty()) {
ListNode top = pq.poll();
if (top.next != null) {
pq.offer(top.next);
}
tail.next = top;
tail = tail.next;
tail.next = null;
}
return dummy.next;
}
}
