题解 | #合并k个已排序的链表#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode *listarr[5000];
    int fifo[listsLen];
    int i;
    struct ListNode *head = NULL;
    int idx = 0;
    int min;
    int min_index;
    struct ListNode *curr = NULL;
    memset(listarr, 0, sizeof(struct ListNode *) * 5000);
    for (i = 0; i < listsLen; i++)
        fifo[i] = 1001;
again:
    min_index = -1;
    min = 1001;
    for(i = 0; i < listsLen; i++) {
        curr = lists[i];
        if (fifo[i] == 1001)
            fifo[i] = (curr != NULL) ? curr->val : 1001;
        if (fifo[i] < min) {
            min_index = i;
            min = fifo[i];
        }
    }
    if (min_index == -1)
        goto out;
    listarr[idx++] = lists[min_index];
    lists[min_index] = lists[min_index]->next;
    fifo[min_index] = (lists[min_index] == NULL) ? 1001 : lists[min_index]->val;
    goto again;
out:
    if (idx == 0)
        return NULL;
    head = listarr[0];
    for (i = 0; i < idx; i++) {
        listarr[i]->next = (i == idx - 1) ? NULL : listarr[i + 1];
    }
    return head;
}