Merge k Sorted Lists

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

 

多路归并。

1、用make_heap函数维护一个大小为k的最小堆。

注：由于默认是最大堆，因此需要自定义compare函数。

注意：comp需要定义为static或者全局函数，因为make_heap、pop_heap、push_heap都是全局库函数。

2、取出最小元素（即lists[0]），用pop_heap函数将最小元素移到最后

3、若原lists[0]，即当前的lists[last]还有后继结点，则用push_heap将其后继结点调整入堆。

否则该链表归并完毕，删除。

 

重复2、3直到所有链表都归并完毕。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    static bool comp(ListNode* l1, ListNode* l2)    {        return l1->val > l2->val;   // min heap    }        ListNode *mergeKLists(vector
     
       &lists) {        ListNode* newhead = new ListNode(-1);        ListNode* tail = newhead;        //remove empty list first        vector
      
       ::iterator it = lists.begin();        while(it != lists.end())        {            if(*it == NULL)                lists.erase(it);            else                it ++;        }                //init heap        make_heap(lists.begin(), lists.end(), comp);        while(!lists.empty())        {            //move the min to the end and adjust            pop_heap(lists.begin(), lists.end(), comp);            ListNode* curmin = lists[lists.size()-1];            lists.pop_back();            if(curmin->next != NULL)            {                lists.push_back(curmin->next);                //add the new element to the heap and adjust                push_heap(lists.begin(), lists.end(), comp);            }            tail->next = curmin;            tail = tail->next;            tail->next = NULL;        }        return newhead->next;    }};