[leetcode] 23: Merge k Sorted Lists.cpp

/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
  // Merge two sorted linked list
  static ListNode *merge(ListNode *a, ListNode *b) {
    ListNode *zero = nullptr, **link = &(zero);
    while (a && b) {
      auto &p = (a->val < b->val) ? a : b;
      *link = std::exchange(p, p->next);
      link = &((*link)->next);
    }
    *link = (a) ? a : (b) ? b : nullptr;
    return zero;
  }

  ListNode *Recursive(const vector<ListNode *> &lists) {
    switch (lists.size()) {
    case 0:
      return nullptr;
    case 1:
      return lists.front();
    default: {
      auto a = std::begin(lists), b = std::end(lists),
           m = std::next(a, std::distance(a, b) / 2);
      //   m = std::midpoint(a, b); // Cpp20
      return merge(Recursive({a, m}), Recursive({m, b}));
    }
    }
  }

  ListNode *Iterative(vector<ListNode *> &lists) {
    int n = lists.size();
    for (int len = 2; len <= 2 * n; len *= 2) {
      for (int i = 0, j = i + len / 2; j < n; i += len, j += len) {
        lists[i] = merge(lists[i], lists[j]);
      }
    }
    return n ? lists[0] : 0;
  }

  ListNode *STL(vector<ListNode *> &lists) {
    return std::reduce(/*std::execution::par,*/ std::begin(lists),
                       std::end(lists), static_cast<ListNode *>(nullptr),
                       Solution::merge);
  }

public:
  ListNode *mergeKLists(vector<ListNode *> &lists) { return Iterative(lists); }
};