/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

int comp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    if(listsSize == 0) return NULL;
    int i, k;
    for(i = 0, k = 0; i<listsSize; ++i)
    {
        if(lists[i])
        {
            struct ListNode *tmpHead = lists[i];
            while(tmpHead)
            {
                k++;
                tmpHead = tmpHead->next;
            }
        }
    }
    if(k==0) return NULL;
    int *nums = (int *)malloc(sizeof(int) * k);
    i = 0, k=0;
    while(i<listsSize)
    {
        if(lists[i])
        {
            struct ListNode *tmpHead = lists[i];
            while(tmpHead)
            {
                nums[k++] = tmpHead->val;
                while(!tmpHead->next && i<listsSize-1)
                {
                    tmpHead->next = lists[++i];
                }
                tmpHead = tmpHead->next;
            }
        }
        ++i;
    }
    qsort(nums, k, sizeof(int), comp);
    i = 0;
    while(!lists[i++]);
    struct ListNode *result = lists[i-1];
    struct ListNode *head = result;
    for(i = 0; i<k;++i)
    {
        head->val = nums[i];
        head = head->next;
    }
    return result;
}