Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

分析

合并k個(gè)已排序的鏈表血巍，并分析時(shí)間復(fù)雜度耻蛇。k為可大可小的參數(shù)硼啤，表示需要合并的鏈表數(shù)目。
自定義一個(gè)Heap類(lèi)：

• vector<ListNode*> heap成員變量作為最小堆根吁。
• vector<ListNode*> indexHeap記錄最小堆內(nèi)各元素來(lái)自于lists中的那個(gè)鏈表。與最小堆heap內(nèi)的元素一一對(duì)應(yīng)嫉拐。
• Heap(vector<ListNode*>& lists);構(gòu)造Heap對(duì)象沃暗，抽取lists各鏈表頭部的第一個(gè)元素瞎颗。
• void push(ListNode*, int);向heap中插入一個(gè)元素件甥，對(duì)應(yīng)地向indexHeap中插入其鏈表編號(hào)捌议。
• int pop();刪除堆頂元素并調(diào)整堆，同時(shí)返回刪除元素所在的鏈表編號(hào)引有，下一步可以在該鏈表中抽取下一個(gè)元素瓣颅。
• ListNode* front();返回堆頂元素(不刪除)。
• bool empty();返回堆是否為空譬正。
• adjustUp(int index);將堆中編號(hào)為index的元素向上調(diào)整宫补。
• adjustDown(int index);將堆中編號(hào)為index的元素向下調(diào)整。

時(shí)間復(fù)雜度：設(shè)第i個(gè)鏈表的長(zhǎng)度為ni曾我，則時(shí)間復(fù)雜度為O(sum(ni)*logk)粉怕。每從堆中取出一個(gè)節(jié)點(diǎn)，需要O(logk)調(diào)整堆抒巢，最壞情況總共需要sum(ni)次調(diào)整贫贝。

注意

• 當(dāng)lists中某鏈表已經(jīng)完全插入到合并鏈表中時(shí)，應(yīng)避免向堆中插入NULL蛉谜。
• adjustDown中循環(huán)體應(yīng)注意s != index稚晚，否則會(huì)進(jìn)入死循環(huán)，詳見(jiàn)代碼型诚。

AC代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Heap {
public:
    Heap(vector<ListNode*>& lists) {
        for (int i = 0; i != lists.size(); ++i) {
            if (lists[i]) {
                push(lists[i], i);
                lists[i] = lists[i]->next;
            }
        }
        // for (int i = heap.size() - 1; i >= 0; --i) {
        //  adjustDown(i);
        // }
    }
    int size() {
        return heap.size();
    }
    bool empty() {
        return heap.empty() && indexHeap.empty();
    }
    void push(ListNode* pointer, int index) {
        heap.push_back(pointer);
        indexHeap.push_back(index);
        adjustUp(heap.size() - 1);
    }
    int pop() {
        int index = indexHeap.front();
        heap.front() = heap.back();
        indexHeap.front() = indexHeap.back();
        heap.pop_back();
        indexHeap.pop_back();
        adjustDown(0);
        return index;
    }
    ListNode* front() {
        return heap.front();
    }
private:
    vector<ListNode*> heap;
    vector<int> indexHeap;
    void adjustDown(int index) {
        if (heap.empty()) {
            return;
        }
        ListNode* save = heap[index];
        int saveIndex = indexHeap[index];
        for (int s = index * 2 + 1; s < heap.size(); s = s * 2 + 1) {
            if (s + 1 < heap.size() && heap[s]->val > heap[s+1]->val) {
                s += 1;
            }
            if (heap[s]->val < save->val) {
                heap[index] = heap[s];
                indexHeap[index] = indexHeap[s];
                index = s;
            } else {
                break;
            }
        }
        heap[index] = save;
        indexHeap[index] = saveIndex;
    }
    void adjustUp(int index) {
        ListNode* save = heap[index];
        int saveIndex = indexHeap[index];
        for (int s = (index - 1) / 2; s >= 0 && s != index; s = (s - 1) / 2) {
            if (heap[s]->val > save->val) {
                heap[index] = heap[s];
                indexHeap[index] = indexHeap[s];
                index = s;
            } else {
                break;
            }
        }
        heap[index] = save;
        indexHeap[index] = saveIndex;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* root = NULL, *current;
        Heap heap(lists);
        while (!heap.empty()) {
            if (root) {
                current->next = heap.front();
                current = current->next;
            } else {
                root = current = heap.front();
            }
            int index = heap.pop();
            if (lists[index]) {
                heap.push(lists[index], index);
                lists[index] = lists[index]->next;
            }
        }
        return root;
    }
};