struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *mergeTwoList(struct ListNode *list1, struct ListNode *list2) {
    struct ListNode *newList;
    struct ListNode *tail;
    if (list1->val <= list2->val) {
        newList = list1;
        tail = list1;
        list1 = list1->next;
    }
    else {
        newList = list2;
        tail = list2;
        list2 = list2->next;
    }

    while (list1 != NULL && list2 != NULL) {
        if (list1->val < list2->val) {
            tail->next = list1;
            tail = list1;
            list1 = list1->next;
        }
        else {
            tail->next = list2;
            tail = list2;
            list2 = list2->next;
        }
    }
    if (list1 == NULL) {
        tail->next = list2;
    }
    else if (list2 == NULL) {
        tail->next = list1;
    }

    return newList;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    int index = -1;
    struct ListNode *res;
    if (listsSize == 0) return 0;
    while (index < listsSize - 1 && lists[++index] == NULL);
    if ( index == listsSize) return NULL;
    res = lists[index];

    for (int i = index + 1; i < listsSize; i++) {
        if (lists[i] != NULL) {
            res = mergeTwoList(res, lists[i]);
            struct ListNode *t = res;
        }
    }

    return res;
}