23. 合并 K 个升序链表

class Solution {
  static ListNode *MergeTwoLists(ListNode *A, ListNode *B) {
    ListNode Dummy;
    ListNode *Prev = &Dummy;

    while (A && B) {
      if (A->val < B->val) {
        Prev->next = A;
        Prev = Prev->next;
        A = A->next;
      } else {
        Prev->next = B;
        Prev = Prev->next;
        B = B->next;
      }
    }
    if (A)
      Prev->next = A;
    if (B)
      Prev->next = B;

    return Dummy.next;
  }

public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty())
      return {};
    return std::reduce(std::next(lists.begin()), lists.end(), lists[0], MergeTwoLists);
  }
};

ListNode* merge(vector <ListNode*> &lists, int l, int r) {
	if (l == r) return lists[l];
	if (l > r) return nullptr;
	int mid = (l + r) >> 1;
	return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
	return merge(lists, 0, lists.size() - 1);
}

class Solution {
  struct ListNodeComparator {
    bool operator()(ListNode *Lhs, ListNode *Rhs) {
      return Lhs->val > Rhs->val;
    }
  };

  priority_queue<ListNode *, vector<ListNode *>, ListNodeComparator> PQ;

public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode Dummy;
    for (auto Head : lists) {
      if (Head)
        PQ.push(Head);
    }

    ListNode *Prev = &Dummy;
    while (!PQ.empty()) {
      ListNode *Smallest = PQ.top();
      PQ.pop();

      Prev->next = Smallest;
      Prev = Prev->next;
      // Keep in mind that we're processing LISTS, not NODES, so we need to
      // manually push tails into the queue.
      if (Smallest->next)
        PQ.push(Smallest->next);
    }
    return Dummy.next;
  }
};

class Solution {
  ListNode *Merge(ListNode *L1, ListNode *L2) {
    ListNode Dummy(0, L1), *Prev = &Dummy;
    while (L1 && L2) {
      if (L1->val < L2->val) {
        Prev->next = L1;
        L1 = L1->next;
      } else {
        Prev->next = L2;
        L2 = L2->next;
      }
      Prev = Prev->next;
    }
    if (L1)
      Prev->next = L1;
    if (L2)
      Prev->next = L2;
    return Dummy.next;
  }

  ListNode *MergeSort(vector<ListNode *>& V, int L, int R) {
    if (L == R)
      return nullptr;
    if (L + 1 == R)
      return V[L];
 
    int M = L + (R - L) / 2;
    ListNode *Left = MergeSort(V, L, M);
    ListNode *Right = MergeSort(V, M, R);
    // No need to break the chain here, since we're processing VECTOR of nodes,
    // not a whole sequence of a list!
    return Merge(Left, Right);
  }

public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    return MergeSort(lists, 0, lists.size());
  }
};

class Solution {
  struct Compare {
    bool operator()(const ListNode *Lhs, const ListNode *Rhs) {
      // Keep in mind that priority_queue default to MAXIMUM heap!
      return Lhs->val > Rhs->val;
    }
  };
public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode *, vector<ListNode *>, Compare> PQ;
    // Push heads ONLY, not all elements altogether.
    for (ListNode *Head : lists) {
      // Avoid pushing null heads.
      if (Head)
        PQ.push(Head);
    }

    ListNode Dummy, *Prev = &Dummy;
    while (!PQ.empty()) {
      // Get smallest HEAD, not smallest elements THEMSELVES. We're doing this
      // because we only connect to the first element of each list. we won't
      // connect them altogether.
      ListNode *Smallest = PQ.top();
      PQ.pop();
      // Form the ordered list using Prev.
      Prev->next = Smallest;
      Prev = Prev->next;
      // Consume the smallest element, and push back into the queue. Note that
      // we won't push nullptrs. We don't need to care about the tail since
      // every list in given vector is null-terminated already.
      if (Smallest->next)
        PQ.push(Smallest->next);
    }
    return Dummy.next;
  }
};