# LeetCode 23: Merge k Sorted Lists

#### Use an array to judge if the list is valid (not null) and an integer to count the invalids

int* valid = (int*)malloc(sizeof(int) * listsSize);
int invalid = 0;
for (int i = 0; i < listsSize; i++) {
    if (lists[i] == NULL) {
        valid[i] = 0;
        invalid++;
    } else {
        valid[i] = 1;
    }
}

#### While invalid didn't reach the maximum, pick the smallest value from all the valid list

int min = 10001; // maximum number for the value
int min_index;
for (int i = 0; i < listsSize; i++) {
    if (valid[i]) {
        if (lists[i]->val < min) {
            min = lists[i]->val;
            min_index = i;
        }
    }
}

#### Judge if it's the first one
If yes, connect it to both the head and tail.
If no, connect the tail to the next one.

if (head == NULL) { // first one
    head = lists[min_index];
    tail = lists[min_index];
} else {            // not the first one
    tail->next = lists[min_index];
    tail = tail->next;
}

#### Judge if the invalids should be added

if (lists[min_index] == NULL) {
    valid[min_index] = 0;
    invalid++;
}

# Done

::: spoiler Raw Code

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    int* valid = (int*)malloc(sizeof(int) * listsSize);
    int invalid = 0;
    for (int i = 0; i < listsSize; i++) {
        if (lists[i] == NULL) {
            valid[i] = 0;
            invalid++;
        } else {
            valid[i] = 1;
        }
    }
    while (invalid != listsSize) {
        int min = 10001;
        int min_index;
        for (int i = 0; i < listsSize; i++) {
            if (valid[i]) {
                if (lists[i]->val < min) {
                    min = lists[i]->val;
                    min_index = i;
                }
            }
        }
        if (head == NULL) {
            head = lists[min_index];
            tail = lists[min_index];
        } else {
            tail->next = lists[min_index];
            tail = tail->next;
        }
        lists[min_index] = lists[min_index]->next;
        if (lists[min_index] == NULL) {
            valid[min_index] = 0;
            invalid++;
        }
    }
    return head;
}

:::