#include "s0023_merge_k_sorted_lists.hpp"

ListNode *S0023::mergeTwoLists(ListNode *a, ListNode *b) {
  if (a == nullptr) {
    return b;
  } else if (b == nullptr) {
    return a;
  }
  ListNode dummy;
  ListNode *tail = &dummy;
  while (a != nullptr && b != nullptr) {
    if (a->val > b->val) {
      tail->next = b;
      b = b->next;
    } else {
      tail->next = a;
      a = a->next;
    }
    tail = tail->next;
  }
  if (a == nullptr) {
    tail->next = b;
  } else {
    tail->next = a;
  }
  return dummy.next;
}

// 分治合并
ListNode *S0023::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, 1, mid), merge(lists, mid + 1, r));
}

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