Assuming there are n lists, and average length of lists is k.

Time Complexity : o(nklg(k))

Space Complexity o(k)
public class Solution {
class ListNodeComparator implements Comparator<ListNode> { public int compare(ListNode o1, ListNode o2) { if (o1.val < o2.val) return 1; else if (o1.val == o2.val) return 0; else return 1; } } public ListNode mergeKLists(List<ListNode> lists) { if (lists.size() == 0) //!! if lists.size() == 0, the new PriorityQueue(size, Comparator()) would throw java.lang.iLegalStatement. because size should > 0 return null; PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.size(), new ListNodeComparator()); ListNode dummy = new ListNode(1); dummy.next = null; ListNode tail = dummy; for (ListNode ln : lists) if (ln != null) //!! it is possible that list contains null pq.add(ln); while (pq.size() > 0) { ListNode node = pq.poll(); if (node.next != null) pq.add(node.next); tail.next = node; tail = node; } tail.next = null; return dummy.next; }
}