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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 *基本思路,在合并2个升序链表时,称头节点较小链表为a链表,另一个链表为b,后续链表b将通过双指针并入链表a:
 *定义移动指针初始指向链a头,移动指针向前遍历同时与链b头比较大小,保证链表a上被遍历部分链表总小于等于链表b;
 *若移动指针遇到更大值,截断后续链表成为新的链b,原链b接入链a末,移动指针重复上述过程继续向前遍历比较;
 *当链a被遍历完毕,将剩余链b直接接入链a末端,得到完整结果链a.
 
 *合并k个升序链表时,基于上述思路,堆排辅助:
 *先排空,里面有空链表;
 *对k个非空链表头指针列表lists进行最小堆排序,取top为链a头,移动指针依旧初始指向链a头;
 *剩余k-1链为准链b,取堆顶链表为链b,
 *移动指针保持比较遍历,比较对象为最小堆lists的top;
 *若移动指针遇到更大值,截断后续链表插入最小堆,原链b接入链a末(从堆中删除),重复比较遍历;
 *若链a被遍历完毕,将链b接入链a,堆空就结束,否则移动指针继续上述操作.
 */
#include <vector>
class Solution {
  private:
    bool is_heap_empty(vector<ListNode*>& lists) {
        return lists.size() <= 1;
    }
    ListNode* heap_pop(vector<ListNode*>& lists) {
        if (is_heap_empty(lists))return nullptr;
        ListNode* tmp = lists[1];
        int n = lists.size() - 2;
        int i = 2;
        while (i <= n) {
            if (i < n && ((((lists[i])->val) > (lists[i + 1])->val)))i++;
            if (((lists[n + 1])->val) > ((lists[i])->val)) {
                lists[i >> 1] = lists[i];
                i <<= 1; //下滤
            } else break;
        }
        lists[i >> 1] = lists[n + 1];
        lists.pop_back();
        return tmp;
    }
    void heap_push(vector<ListNode*>& lists, ListNode* ptr) {
        int n = lists.size();
        int i = n;
        lists.emplace_back(nullptr);
        while (i > 1 && (((lists[i >> 1])->val) > (ptr->val))) {
            lists[i] = lists[i >> 1];
            i >>= 1; //上滤
        }
        lists[i] = ptr;
    }
    ListNode* heap_top(vector<ListNode*>& lists) {
        if (is_heap_empty(lists))return nullptr;
        else return lists[1];
    }

  public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        int n = lists.size();
        //去除nullptr
        {
            int i = 0, cnt = 0;
            while (i < n - cnt) {
                if (lists[i] == nullptr) {
                    cnt++;
                    lists[i] = lists.back();
                    lists.pop_back();
                    continue;
                }
                i++;
            }
        }

        //特殊情况
        n = lists.size();
        if (n == 0)return nullptr;
        if (n == 1)return lists[0];

        //最小堆调整: i>=1,父节点No.i的,左孩子为No.2i,右孩子为No.2i+1;
        ListNode* tmp = nullptr;
        lists.emplace(lists.begin(), nullptr); //now size is n+1
        for (int i = n >> 1, j = 0; i > 0; i--) {
            tmp = lists[i];
            j = i << 1;
            while (j <= n) {
                if (j < n && (((lists[j])->val) > ((lists[j + 1])->val)))j++;
                if ((tmp->val) > ((lists[j])->val)) {
                    lists[j >> 1] = lists[j];
                    j <<= 1;//下滤
                } else break;
            }
            lists[j >> 1] = tmp;
        }
        lists[0] = lists[1]; //哨兵位

        //遍历合并各链表
        ListNode* dPtr = heap_pop(
                             lists); //移动指针,初始化为最小端链头,同时pop
        ListNode* sPtr = heap_top(lists); //固定指针
        while (true) {
            while (dPtr->next != nullptr && ((dPtr->next->val) <= (sPtr->val)))
                dPtr = dPtr->next;
            //dPtr->next == nullptr || dPtr->next->val > sPtr->val
            if (dPtr->next == nullptr) {
                dPtr->next = heap_pop(lists);
                sPtr = heap_top(lists);
                if (sPtr == nullptr)break;
                else continue;
            }
            tmp = heap_pop(lists);
            heap_push(lists, dPtr->next);
            dPtr->next = tmp;
            sPtr = heap_top(lists);
        }
        return lists[0];
    }
};