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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
//本题的解决思路来自左神的算法讲解027中所讲的第一题
void swap(struct ListNode** arr , int i , int j){
    struct ListNode* temp = arr[i];//交换这个两个节点的指针
    arr[i] = arr[j];
    arr[j] = temp;
}
void heapInsert(struct ListNode** arr , int i){
    while(arr[i]->val < arr[(i - 1) / 2]->val){
        swap(arr , i , (i - 1) / 2);
        i = (i - 1) / 2;
    }
}
void heapify(struct ListNode** arr , int i , int size){
    int l = i * 2 + 1;
    while(l < size){
        int best = l + 1 < size && arr[l + 1]->val < arr[l]->val ? l + 1 : l;
        best = arr[i]->val < arr[best]->val ? i : best;
        if(best == i) break;
        swap(arr , i , best);
        i = best;
        l = i * 2 + 1;
    }
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    struct ListNode* arr[5001];
    int size = 0;//用size表示堆的大小
    struct ListNode* head = NULL , *pre = NULL;
    for(int i = 0;i < listsLen;i++){
        pre = *(lists + i);//让pre指向lists中每个链表的头节点
        if(pre != NULL) {//当pre所指向的那个链表不是空链表时，把pre指向的节点放进堆里
            arr[size++] = pre;
            heapInsert(arr , size - 1);//保证每次堆里增加一个头节点后，根据头结点的值，arr仍为小根堆
        }
    }//通过向上调整的方法建立堆结构
    if(0 == size) return NULL;//判断堆里面有无链表
    head = pre = arr[0];//弹出堆的顶部节点（堆的最小值）作为新的链表的头部节点
    if(pre->next != NULL) arr[0] = pre->next;
    else swap(arr , 0 , --size);
    while(size > 0){
        heapify(arr , 0 , size);//传入参数：堆，要进行向下调整的节点的索引，堆的大小
        pre->next = arr[0];//新链表链接堆中的最小值
        pre = pre->next;
        if(arr[0]->next != NULL) arr[0] = arr[0]->next;//判断这一链表是否还有节点
        else swap(arr , 0 , --size);//如果没有了，那么就无视掉
    }
    pre->next = NULL;//给新链表的结尾连到NULL
    return head;//返回新链表的头部节点
}