//
//  Solution23.cpp
//  Algorithm
//
//  Created by Pancf on 2020/10/12.
//  Copyright © 2020 Pancf. All rights reserved.
//

#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;
    }
}

// k = lists.size(), n = average list, 时间复杂度 = k/2 * 2n + k/4 * 4n + ... + 1 * kn = kn * logk
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();
}