题解 | 合并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 ) {
    struct ListNode list1MastHeadNode = { .next = lists[0] };
    struct ListNode listTmpHeadNode;
    struct ListNode *pListMst = list1MastHeadNode.next;
    struct ListNode *pListMstPre = &list1MastHeadNode;
    struct ListNode *pListTmp = NULL;

    if ((lists == NULL) || (listsLen == 0)) {
        return NULL;
    }
    if (listsLen == 1) {
        return lists[0];
    }
    //思路
    //以第一条链为主链，依次与后面的链表两两进行重组合并

    for (size_t i = 1; i < listsLen; i++) {
        //将主链的操作指针复位
        pListMst = list1MastHeadNode.next;
        pListMstPre = &list1MastHeadNode;

        //指定副链的指针
        listTmpHeadNode.next = lists[i];
        pListTmp = listTmpHeadNode.next;

        while ((pListMst != NULL) && (pListTmp != NULL)) {
            if (pListMst->val >= pListTmp->val) {
                //将结点插入主链
                listTmpHeadNode.next = pListTmp->next;
                pListTmp->next = pListMst;
                pListMstPre->next = pListTmp;
                pListTmp = listTmpHeadNode.next;
                pListMstPre = pListMstPre->next;
            } else {
                //继续遍历主链
                pListMst = pListMst->next;
                pListMstPre = pListMstPre->next;
            }
        }
        if (pListMst == NULL) {
            //遍历主链结束后，将副链剩余结点连接在主链尾部
            pListMstPre->next = pListTmp;
        }
    }
    return list1MastHeadNode.next;
}