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

#include <algorithm>
#include <vector>

class Solution {
 public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * @ comment:
   * 1. 该问题的关键是使用堆函数，实现logN的排序; 同时对Comp比较的本质有所体会。
   * 2. 默认的comp是使用less<>()完成大堆序，即<,若要实现小堆序，就要用>=。
   * 3. 初始化堆的使用make_heap，之后的pop_heap和push_heap其内部都存在make_heap操作；
   * 4. 还有就是这三者的Comp需要一致；
   * @param lists ListNode类vector
   * @return ListNode类
   */
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return nullptr;
    std::vector<ListNode*> data;
    auto Comp = [](const ListNode * lhs, const ListNode * rhs) {
      return lhs->val >= rhs->val;
    };
    for (auto& item : lists) {
      if (item == nullptr) continue;
      data.push_back(item);
    }

    auto head = new ListNode(-1);
    auto p = head;
    std::make_heap(data.begin(), data.end(), Comp);
    while (!data.empty()) {
      std::pop_heap(data.begin(), data.end(), Comp);
      auto min_value = data.back();
      p->next = min_value;
      p = p->next;
      if (min_value->next == nullptr)
        data.pop_back();
      else
        data.back() = min_value->next;
      std::push_heap(data.begin(), data.end(), Comp);
    }

    auto ret = head->next;
    delete head;
    return ret;
  }
};