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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
#include <stdlib.h>
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    //空数组直接返回
    if(listsLen==0)
        return NULL;
    /*
		n用来遍历数组
		val用来存放最小值
		numofnull用来统计空链表数量，与链表总数相同则结束
		numofsmall用来记录最小头节点位置
		newhead作为哨兵位，newhead->next指向新链表头节点
		newtail指向新链表尾节点
	*/
    int n,val,numofnull=0,numofsmall;
    struct ListNode* newhead=malloc((sizeof(struct ListNode)));
    struct ListNode* newtail=newhead;
   //数组中空链表数量小于链表总数，找头节点最小的链表
    while(numofnull<listsLen)
    {
	    //空链表数量清零，最小值重置
        numofnull=0;
        val=1001;
	   //遍历链表数组
        for(n=0;n<listsLen;n++)
        {
            //第n个链表不为空
            if(lists[n])
                {
                    //第n个链表的头节点小于最小值
                    if(lists[n]->val<val)
                    {
                        numofsmall=n;
                        val=lists[n]->val;
                    }
                }
            else 
                numofnull++;
        }
	   //链表不全为空时，最小头节点尾插至新链表
        if(numofnull<listsLen)
        {
            newtail->next=lists[numofsmall];
            lists[numofsmall]=lists[numofsmall]->next;
            newtail=newtail->next; 
        }       
    }
   //链表全为空，合并结束newtail指向新链表头节点，释放newhead
    newtail=newhead->next;
    free(newhead);
    return newtail;  
}