学步园

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

两种实现方法，第一种采用优先队列，第二种采用分治

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /**
     * use priority_queue
    class mycomparison
    {
    public:
        bool operator() (ListNode* lhs, ListNode* rhs)
        {
                return (lhs->val > rhs->val);
        }
    };
    
    ListNode *mergeKLists(vector<ListNode*> &lists) {
        
        priority_queue<ListNode*, vector<ListNode *>, mycomparison>  queue;
        for(int i = 0; i < lists.size(); i++){
            if(lists[i] != NULL)
                queue.push(lists[i]);
        }
        
        ListNode* head =NULL;
        ListNode* prev = NULL;
        while(!queue.empty())    
        {
            ListNode* tmp = queue.top();
            queue.pop();
            if(!prev)
            {
                head = tmp;
                prev = tmp;
            }
            else
            {
                prev->next= tmp;
                prev = tmp;
            }
            if(tmp->next)
                queue.push(tmp->next);
            
        }
        return head;
    }
    */
    //use divide and conquer algorithm
    //merge two list
    ListNode* Merge(ListNode* list1, ListNode* list2)
    {
        ListNode* head = NULL;
        if(list1 == NULL)
            return list2;
        if(list2 == NULL)
            return list1;
        if(list1->val < list2->val){
            head = list1;
            head->next = Merge(list1->next, list2);
        }    
        else{
            head = list2;
            head->next = Merge(list1, list2->next);
        }
        return head;
    }
    ListNode* MergeCore(vector<ListNode*> &lists, int left, int right)
    {
        if(left < right)
        {
            int mid = (right+left)/2;
            return Merge(MergeCore(lists, left, mid), MergeCore(lists, mid+1, right));
        }
        else if(left == right)
            return lists[left];
        return NULL;    
    }
    ListNode *mergeKLists(vector<ListNode*> &lists) {
        if(lists.size() <= 0)
            return NULL;
        return MergeCore(lists, 0, lists.size()-1);
    }
};