# Share My C code in 13ms, use min-heap.

• In this problem, input is linked lists; divide an conquer works good.

But if we need to sort arrays or vectors, divide and conquer will spend too much extra space.

So I think, maybe heap (or loser tree) is a better method.(when K is big enough)

The time complexity is O(k) + O(nlgk). (divide and conquer is exactly n*lg(k), more comparison times)

``````void MIN_HEAP_SORT(struct ListNode **lists, int index_i,int size)
{
int left = index_i*2 + 1;
int right= index_i*2 + 2;
if(left>=size)
return;
int min;
if(right>=size)
min = left;
else
min = lists[left]->val<lists[right]->val?left:right;
if(lists[index_i]->val>lists[min]->val){
struct ListNode *temp = lists[index_i];
lists[index_i] = lists[min];
lists[min] = temp;
MIN_HEAP_SORT(lists,min,size);
}
}

void BuildHeap(struct ListNode **lists,int size)
{
for(int i=(size-1)/2;i>=0;--i){
MIN_HEAP_SORT(lists,i,size);
}
}

struct ListNode *mergeKLists(struct ListNode *lists[], int k) {
if(k==0)
return NULL;//1
struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode *int_max = (struct ListNode*)malloc(sizeof(struct ListNode));
int_max->val = INT_MAX;
int_max->next = NULL;
for(int i=0;i<k;++i){
if(lists[i]==NULL)
lists[i] = int_max;
}/*remove those NULL ptr*/
BuildHeap(lists,k);
while(lists[0]!=int_max){
travel->next = lists[0];
travel = lists[0];
lists[0] = lists[0]->next;
if(lists[0]==NULL)
lists[0] = int_max;
MIN_HEAP_SORT(lists,0,k);
}
travel->next = NULL;
}
``````

there is an extra head node, an extra INT_MAX node (used to replace NULL ptr)

• you mean your 392 ms solution -- I did it in C++ with priority_queue and a comparison function on the pointers and it ran in 420 ms -- so I wanted to check if there was another fast C/C++ solution. I checked yours and a few more -- they all run in around 400ms (-20 ms for C, +20ms for C++)

• Some test cases are added.

• I submit my code for merge k sorted list but OJ produce "Last executed input: []" . Can anybody tell me what is it meaning?

• an empty list is passed

• my idea is just like you, but at first I did not thought the small tips of ListNode max, to reference your code, my solution passed in 9 ms, thank you very much
'''
//将当前值调节入
void adjustTree(struct ListNode** lists, int listSize, int index)
{
int resultIndex = 0;
int leftIndex = index * 2 + 1;
int rightIndex = index * 2 + 2;

``````if(leftIndex >= listSize)
return;

int indexValue = lists[index]->val;
int leftValue = lists[leftIndex]->val;
int rightValue = (rightIndex) >= listSize ? INT_MAX : lists[rightIndex]->val;

if(leftValue <= rightValue)
{
//此时进行交换
if(indexValue > leftValue)
{
struct ListNode* temp = lists[index];
lists[index] = lists[leftIndex];
lists[leftIndex] = temp;
resultIndex = leftIndex;
}

} else
{
if(indexValue > rightValue)
{
struct ListNode* temp = lists[index];
lists[index] = lists[rightIndex];
lists[rightIndex] = temp;
resultIndex = rightIndex;
}
}
``````

}

//建立小顶堆的过程
void buildTree(struct ListNode** lists, int listSize)
{
//建树的过程要从下标 (n-1)/2 处开始
int begin = (listSize-1) / 2;
for(int index = begin; index >= 0; index--)

}

//此处理解lists应该认为是所有的list的头的合集
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{

``````struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* max = (struct ListNode*)malloc(sizeof(struct ListNode));
max->val = INT_MAX;
max->next = NULL;

if(listsSize == 0)
return NULL;

//设置一个最大的堆，用于替代链表最后的空值.
for(int i = 0; i < listsSize; i++)
{
if(lists[i] == NULL)
lists[i] = max;
}
//以k个头结点建立小顶堆
buildTree(lists, listsSize);

while (lists[0] != max)
{
cur->next = lists[0];
cur = lists[0];
lists[0] = lists[0]->next;

if(lists[0] == NULL)
lists[0] = max;