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

C语言

//根据索引获得链表的元素
int getListElemByIndex(struct ListNode* list, int index){
    for(int i=0; i<index; i++)
        list = list->next;
    return list->val;
}

//计算数组指定长度的前N项和
int getSumLen(int *eachLen, int listsLen){
    int sumLen = 0;
    for(int i=0; i<listsLen; i++){
        sumLen += eachLen[i];
    }
    return sumLen;
}
//找到链表首部最小的值，并返回链表索引
int findListHeadMin(struct ListNode** lists, int listsLen, int* eachIndex, int* eachLen){
    int listIndex = 0;
    int listNodeMin = 1001;
    int tmpVal;
    struct ListNode* tmpList;
    for(int i=0; i<listsLen; i++){
        if(eachIndex[i] >= eachLen[i])continue; //如果该链表已经用完，跳过
        
        tmpVal = getListElemByIndex(lists[i], eachIndex[i]);
        if(tmpVal < listNodeMin){
            listNodeMin = tmpVal;
            listIndex = i;
        }
    }
    return listIndex;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* tmpNode = dummyHead;
    int *eachLen = (int*)malloc(sizeof(int)*listsLen);  //保存各个链表的长度
    int *eachIndex = (int*)malloc(sizeof(int)*listsLen);  //保存各个链表的索引
    int sumLen = 0;//各个链表相加的总长度
    int listMinIndex; //各个链表中当前节点值最小的链表索引

    for(int i=0; i<listsLen; i++){      //获得各个链表的长度
        int len = 0;
        eachLen[i] = 0;
        eachIndex[i] = 0;           //清空索引
        struct ListNode* tmp = *(lists + i);
        while(tmp){
            eachLen[i]++;
            tmp = tmp->next;
        }
    }
    sumLen = getSumLen(eachLen, listsLen);  //计算各个链表的元素总和
    if(sumLen == 0) return NULL;            //如果 0个链表 或者 有多个链表但每个链表都为空，则返回NULL
    for(int curLen=0; curLen<sumLen; curLen++){ //根据元素总和进行循环
        tmpNode->val = 0;               //先初始化当前链表值

        listMinIndex = findListHeadMin(lists, listsLen, eachIndex, eachLen);    //找到各个链表中未使用的首元素最小的链表索引
        tmpNode->val = getListElemByIndex(lists[listMinIndex], eachIndex[listMinIndex]);    //根据链表以及链表索引找到未使用的元素
        eachIndex[listMinIndex]++;                      //记录当前链表已使用的元素数量，方便findListHeadMin函数判断未使用的元素以及是否到末尾了

        if(curLen==sumLen-1)continue;           //如果已经到最后一个元素，那么不再申请节点
        tmpNode->next = (struct ListNode*)malloc(sizeof(struct ListNode));    //初始化新节点
        tmpNode = tmpNode->next;    //指向下一个节点
    }

    return dummyHead;
}