leecode 題解 || Merge k Sorted Lists 問題

problem：

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

Tags Divide and Conquer Linked List Heap
           

合并K個已序單連結清單

thinking：

 （1）題目沒有要求不可以新開ListNode,是以暴力破解法：提取K個list的關鍵字，排序、建立結點插入。這種情況對原list是否排好序沒有要求。

         排序時間複雜度可以做到O(N* log N )，提取關鍵字和建立結點的時間複雜度都為O（N），是以總的時間複雜度為O（N*logN），這沒有考慮建立結點的時間浪費和空間           浪費。

（2）采用可以容納結點的容器，想到的是堆，或者堆的封裝-優先隊列，由于堆的O(N*logN)排序的時間複雜度，而且不用新開結點，節省空間。

暴力法：

/**
 * 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) {
        ListNode *newlist=NULL;
        vector<int> tem;
        for(int i=0;i<lists.size();i++)
        {
            while(lists.at(i)!=NULL)
            {
                tem.push_back(lists.at(i)->val);
                lists.at(i)=lists.at(i)->next;
            }
        }
        if(tem.size()==0)
            return NULL;
        sort(tem.begin(),tem.end());
        for(int i=tem.size()-1;i>=0;i--)
        {
            ListNode *p = new ListNode(tem.at(i));
            p->next = newlist;
            newlist = p;
            
        }
        return newlist;
    }//mergeKLists()

};
           

優先隊列法：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class ListNodeCompare:public binary_function<ListNode*,ListNode*,bool>
{
public:
    bool operator()(ListNode* t1,ListNode* t2)const
    {
        if ( !t1||!t2 )
            return !t2;
        return t1->val>t2->val;
    }
};
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (lists.empty())
            return NULL;
        priority_queue<ListNode*,vector<ListNode*>,ListNodeCompare> Q;
        for(int i=0;i<lists.size();i++)
            if ( lists[i]!=NULL)
                Q.push(lists[i]);
        ListNode guard(-1);
        ListNode* tail=&guard;
        while(!Q.empty())
        {
            ListNode* toAdd=Q.top();
            Q.pop();
            tail->next=toAdd;
            tail=tail->next;
            if (toAdd->next)
                Q.push(toAdd->next);
        }
        return guard.next;
    }
};