#include "Solution23.hpp"

ListNode* merge2Lists(ListNode* l1, ListNode* l2)

{

if (!l1) return l2;

if (!l2) return l1;

if (l1->val < l2->val) {

l1->next = merge2Lists(l1->next, l2);

return l1;

} else {

l2->next = merge2Lists(l1, l2->next);

return l2;

}

}

ListNode* Solution23::mergeKLists(std::vector<ListNode *> &lists)

{

if (lists.size() == 0) return nullptr;

size_t len = lists.size();

while (len > 1) {

for (int i = 0; i < len / 2; ++i) {

lists[i] = merge2Lists(lists[i], lists[len - i - 1]);

}

len = (len + 1) / 2;

}

return lists.front();

}