A java solution based on HeapSort

• ``````import java.util.List;

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/

public class Solution {

/*
* Assume that lists[start..end] satisfy the definition of Heap except for lists[start]
* This function adjust lists[start..end] to Heap
* Note that both start and end index are inclusive, counted from 0
*/
private void heapAdjust(List<ListNode> lists, int start, int end) {
if (start >= end) {
return;
}
ListNode temp = lists.get(start);
for (int i = (start+1)*2-1; i <= end; i = (i+1)*2-1) {
if (i < end && lists.get(i).val > lists.get(i + 1).val) {
i++;
}
if (temp.val <= lists.get(i).val) {
break;
}
lists.set(start, lists.get(i));
start = i;
}
lists.set(start, temp);
}

/*
* There are some tricky sample input: some linked lists are null
* which cause 'mergeKLists' function crash
* so this function process the raw input by removing the null lists from List<ListNode>
*/
private void process(List<ListNode> lists) {
for (int i = 0; i < lists.size(); i++) {
if (lists.get(i) == null) {
lists.remove(i);
i--;
}
}
}

public ListNode mergeKLists(List<ListNode> lists) {
ListNode newList = null, tail;
process(lists);
if (lists.size() == 0) {
//After 'process' the parameter 'lists' may not have any linked list
//so return a null reference
return newList;
}
//adjusts the whole lists to Heap
for (int i = (lists.size()-2)/2; i >= 0; i--) {
}
newList = lists.get(0);
tail = lists.get(0);
lists.set(0, lists.get(0).next);
while (lists.size() > 0) {
if (lists.get(0) == null) {
if (lists.size() > 1) {
lists.set(0, lists.get(lists.size() - 1));
lists.remove(lists.size() - 1);
}
else {
break;
}
}