minHeap: time - O(nlog(k)), space - O(k), n is total number of all the listnode, k is the length of lists

```
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
return heap(lists);
}
private ListNode heap(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
public int compare(ListNode a, ListNode b) {
return a.val - b.val;
}
});
for (ListNode head : lists) {
if (head != null)
pq.offer(head);
}
ListNode res = new ListNode(0);
ListNode resHead = res;
while (!pq.isEmpty()) {
ListNode cur = pq.poll();
res.next = cur;
res = res.next;
if (cur.next != null) {
pq.offer(cur.next);
}
}
return resHead.next;
}
```

like mergeSort(recursion): time-O(vlog(k)), space- O(log(k)), v is average length of a list, k is length of lists.

```
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
return helper(lists, 0, lists.length - 1);
}
private ListNode helper(ListNode[] lists, int start, int end) {
if (start == end) {
return lists[start];
}
int mid = (start + end) / 2;
ListNode left = helper(lists, start, mid);
ListNode right = helper(lists, mid + 1, end);
return mergeTwo(left, right);
}
private ListNode mergeTwo(ListNode left, ListNode right) {
ListNode head = new ListNode(0);
ListNode newHead = head;
while (left != null && right != null) {
if (left.val <= right.val) {
head.next = left;
left = left.next;
} else {
head.next = right;
right = right.next;
}
head = head.next;
}
if (left != null) {
head.next = left;
}
if (right != null) {
head.next = right;
}
return newHead.next;
}
```