题解 | #合并k个已排序的链表#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        queue<ListNode*> que;
        int n = lists.size();
        if (!n) return nullptr;
        bool flag = true;
        while (flag) {
            flag = false;
            int idx = 0;
            for (int i = 0; i < n; ++i) {
                if (lists[i] != nullptr && !flag) {
                    flag = true;
                    idx = i;
                    continue;
                }
                if (lists[i] != nullptr) {
                    idx = lists[i]->val < lists[idx]->val ? i : idx;
                }
            }
            if (!flag) break;
            que.push(lists[idx]);
            lists[idx] = lists[idx]->next;
        }
        if (que.empty()) return nullptr;;
        ListNode* cur = que.front();
        que.pop();
        ListNode* first = new ListNode(0);
        first->next = cur;
        while (!que.empty()) {
            ListNode* next = que.front();
            que.pop();
            cur->next = next;
            cur = next;
        }
        return first->next;
        // write code here
    }
};