题解 | #牛群的合并#

考察知识点：数组，指针，遍历，链表

解题分析： 这题是需要组成一个新的链表，按升序排列，难点在于怎么从移植的链表数组中拿到一个最小值的，这里我选择遍历链表数组，每次都中数组中获取一个最小的成员出来，并添加到新的链表中；这样就能保证生成的最新链表都是从最小的值开始的

编程语言：C

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    struct ListNode *new_head = NULL, *tmp_head = NULL;
    struct ListNode *min_head = NULL;
    int index = 0;

    while (1) {
        min_head = NULL;
        index = 0;

	  	/* 每次都从链表数组这种取出一个最小的值 */
        for (int i = 0; i < listsLen; i++) {
            if (lists[i] == NULL)
                continue;

            if (min_head == NULL) {		// 如果最小成员没有初始化，就将第一个值初始化给他
                min_head = lists[i];
                index = i;		// 标记当前的值是从哪个链表中获取的
            } else {
                if (lists[i]->val < min_head->val) {		// 如果找到了比当前的最小值更小的值，就更新最小值的地址以及对于的链表id
                    min_head = lists[i];
                    index = i;
                }
            }
        }

        if (min_head == NULL)	// 如果获取到的最小的值是空，就表明所有的链表都遍历到了最后一个成员
            break;

        if (tmp_head == NULL) {		// 如果新的链表没有初始化，就初始化新的链表
            tmp_head = lists[index];
            new_head = tmp_head;		// 标记新链表的链表头
        } else {		// 新链表已经初始化的话，就将获取到的最小的成员添加到新链表中
            tmp_head->next = lists[index];
            tmp_head = tmp_head->next;
        }

        lists[index] = lists[index]->next;		// 更新获取出成员的链表的指针为下一个成员
    }

    if (tmp_head)		// 如果有初始化链表，就给新链表的最后一个成员的下有一个成员赋值为空，防止死循环
        tmp_head->next = NULL;

    return new_head;
}