学步园

Merge k Sorted Lists

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

思路：

标准的merge sort使用min(x,y)，这里需要的是min(x1, x2, ... xk)，可以用堆实现。

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        using node_pair = pair<ListNode*, size_t>;
       
        // Note: By default, C++ will create a max-heap, but we need a min-heap
        auto comparison=[](const node_pair& n1, const node_pair& n2) -> bool {
            return n1.first->val > n2.first->val; 
        };
       
        // starting point of the list
        ListNode* new_start = new ListNode(0);
        ListNode* new_last = new_start;
       
        // Heap, storing the first node of each list
        vector<node_pair> v_nodes;
        v_nodes.reserve(lists.size());
       
        // initalize the heap
        size_t index=0;
        for(auto& t : lists)
        {
            if (t!=nullptr)
            {
                v_nodes.push_back(node_pair(t, index));
                t=t->next;
            }
            index++;
        }
        make_heap(begin(v_nodes), end(v_nodes),comparison);
       
        // Heap injector
        auto inject_heap=[&v_nodes,&lists,&comparison](const size_t list_id) -> void {
            if (lists[list_id]==nullptr)
                return;
            else
            {
                auto save = lists[list_id];
                lists[list_id]=save->next;
                v_nodes.push_back(node_pair(save, list_id));
                push_heap(begin(v_nodes), end(v_nodes), comparison);
            }
        }; 
       
        // Loop until the heap is empty
        while(!v_nodes.empty())
        {
            pop_heap(begin(v_nodes), end(v_nodes), comparison);

            auto t = v_nodes.back();
            v_nodes.pop_back();

            new_last->next = t.first;
            new_last = new_last->next;
           
            inject_heap(t.second);
        }
       
        // drop the head
        new_last=new_start;
        new_start=new_start->next;
        delete new_last;
       
        return new_start;
    }
};