# Java using heap sort

• I guess time complexity is O(N*logK)

class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null) {
return null;
}

``````    int len = lists.length;
int i = 0;
int maxNode = 0;
//lists may have nulls, below loop move non-null at first and re-size. so first len Listnode are not null.
//i.e. lists : [Node1, null, Node2, null, null, Node3] and len is 6, after below loop it becomes [Node1, Node2, Node3, null, null, null] and len is 3.
//When we do heap or sort, we only consider first 3 elements.
while (i < len) {
while (lists[i] == null && len-1 > i) {
lists[i] = lists[len-1];
len--;
}

if (lists[i] == null) {
len--;
} else if (lists[i] != null && lists[i].val > lists[maxNode].val) {
maxNode = i;
}
i++;
}

if (len == 0) {
return null;
}

//build heap, root (0-index element) has smallest val.
for (i = len/2-1; i >= 0; i--) {
heapify(i, len, lists);
}

ListNode dummy = new ListNode(0);
ListNode cur = dummy;

int size = len;
while (size > 0) {
//lists[0] has smallest value so poll it and link it after cur.
cur.next = lists[0];
cur = cur.next;

//Get next Node from list[0] and do heapify, so lists[0] will holds the smallest element.
lists[0] = lists[0].next;

//If there is no next node from lists[0], we exchange last element from lists and reduce size.
if (lists[0] == null) {
size--;
lists[0] = lists[size];
}

heapify(0, size, lists);
}

return dummy.next;
}

private void heapify(int s, int len, ListNode[] lists) {
int min = s;
int left = 2*s + 1;
int right = 2*s + 2;

if (left < len && lists[left] != null && lists[left].val < lists[min].val) {
min = left;
}

if (right < len && lists[right] != null && lists[right].val < lists[min].val) {
min = right;
}

if (min != s) {
ListNode temp = lists[s];
lists[s] = lists[min];
lists[min] = temp;

heapify(min, len, lists);
}
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.