题解 | #牛群的合并#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
int ListsAllNull(struct ListNode** lists, int listsLen)
{
    int num=0;
    for(int i=0;i<listsLen;i++)
    {
        if(!lists[i])
            num++;
    }
    return num==listsLen?0:1;    
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode** p=lists;
    struct ListNode* p1=NULL;
    struct ListNode* head=(struct ListNode*)malloc(sizeof(struct ListNode*));
    struct ListNode* p2=head;
    while (ListsAllNull(p,listsLen)) {
        p1=p[0];
        int f=0;
        for(int i=0;i<listsLen-1;i++){
            //求得当前所指最小值，并把p1指针指向该节点
            int num1=-1,num2=-1;
            num1=p1?p1->val:5001;
            num2=p[i+1]?p[i+1]->val:5001;
            p1=num1>num2?p[i+1]:p1;
            f=num1>num2?i+1:f;
        }
        p[f]=p[f]->next;
        p1->next=NULL;
        p2->next=p1;
        p2=p2->next;
    }
        //该节点指向空，接在head链表
        return head->next;
}

C语言，时间复杂度O（n），空间复杂度o（1）