题解 | #合并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 ) {
    // inputs checking
    if(!lists || listsLen < 2) {
        return *lists;
    }

    struct ListNode* head = 0;
    struct ListNode* p = 0;

    while (listsLen > 1) {
        // find the minimal value
        int minId = -1;
        int minVal = 1000;
        for(int i = 0; i < listsLen; i++){
            struct ListNode* item = *(lists + i);
            // check empty item list
            if (!item){
                listsLen--;
                *(lists + i) = *(lists + listsLen);
                i--; // This is very important
                continue;
            }
            // compare to min
            if (item -> val < minVal){
                minVal = item -> val;
                minId = i;
            }
        }
        // if no avaliable list was found
        if (minId < 0) {
            break;
        }
        struct ListNode* smaller = *(lists + minId);
        // append to tail
        if (!head){
            p = head = smaller;
        } else {
            p->next = smaller;
            p = smaller;
        }
        // check if current list was out of elements
        if (smaller -> next) {
           *(lists + minId) = smaller->next;
        } else {
            listsLen--;
            *(lists + minId) = *(lists + listsLen);
        }
    }
    // append remains to the end
    if (listsLen == 1 && *lists) {
        p->next = *lists;
    }

    return head;
}

1. 常规输入检查
2. 遍历列表，找出有最小值的链表节点， 放到结果链表的后面
3. 如果上述遍历过程，发现为空的链表，则将其与列表最后一条交换，并让 listLen(可用列表长度)减 1
4. 重复遍历，直到 listLen 为 0 或 1
5. 遍历完成后，如果 listLen 仍为 1，则说明还有 1 个链表有值，直接将其 附加到结果列表之后