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

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.empty()) {
            return NULL;
        }
        ListNode *newHead, *newTail;
        bool empty = true;
        int minPos = -1, minVal = 99999;
        for (int i = 0; i < lists.size(); ++i) {
            if (lists[i] != NULL) {
                empty = false;
                if (lists[i]->val < minVal) {
                    minPos = i;
                    minVal = lists[i]->val;
                }
            }
        }
        if (empty) {
            return NULL;
        }
        newHead = lists[minPos];
        newTail = lists[minPos];
        lists[minPos] = lists[minPos]->next;
        newTail->next = NULL;
        // 遍历lists中的元素，找到val最小的结点，若遍历到NULL，则删除该元素。直到元素全部为空
        while (!empty) {
            minPos = -1, minVal = 99999;
            empty = true;
            for (int i = 0; i < lists.size(); ++i) {
                if (lists[i] != NULL) {
                    empty = false;
                    if (lists[i]->val < minVal) {
                        minPos = i;
                        minVal = lists[i]->val;
                    }
                }
            }
            if (empty) {
                break;
            }
            // 找到了最小结点位置
            if (minPos >= 0) {
                newTail->next = lists[minPos];
                lists[minPos] = lists[minPos]->next;
                newTail = newTail->next;
                newTail->next = NULL;
            }
        }
        return newHead;
    }
};