23.Merge k Sorted Lists

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

Merge k Sorted Lists

分析: 這是一道很基本的題, 可以用有限隊(duì)列, 分治法等解決.

優(yōu)先隊(duì)列: C++ STL中有提供優(yōu)先隊(duì)列priority_queue, 是一模板, 聲明如下:

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

注意默認(rèn)的比較策略(policy)是std::less, 此處需要我們提供自己的比較函數(shù), 只需定義一個(gè)仿函數(shù)(functor), 也即重載operator()運(yùn)算符:

struct cmp {
    bool operator()(ListNode* p, ListNode* q) {
        return p->val > q->val;
    }
};

priority_queue的大小始終為k, 每次一個(gè)ListNode經(jīng)過(guò)優(yōu)先隊(duì)列時(shí)調(diào)整的復(fù)雜度為O(lgk), 節(jié)點(diǎn)插入鏈表的復(fù)雜度為O(1), 共有nk個(gè)節(jié)點(diǎn), 故算法復(fù)雜度為O(nklgk), 空間復(fù)雜度為O(k).整個(gè)代碼如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct cmp {
        bool operator()(ListNode* p, ListNode* q) {
            return p->val > q->val;
        }
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> p_queue;
        ListNode* dummy = new ListNode(0), *tail = dummy;
        
        for(int i = 0; i < lists.size(); ++i) {
            if(lists[i]) p_queue.push(lists[i]);
        }
        
        while(!p_queue.empty()) {
            tail->next = p_queue.top();
            tail = tail->next;
            p_queue.pop();
            if(tail->next)
                p_queue.push(tail->next);
        }
        tail = dummy->next;
        delete dummy;
        return tail;
    }
};

分治法: 每次合并兩個(gè)鏈表, 直到只剩一個(gè)鏈表為止. 算法復(fù)雜度為O(nklgk), 空間復(fù)雜度為O(1).

/**
 * 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) {
        if(lists.empty()) return NULL;
        
        int end = lists.size() - 1, begin;
        while(end > 0) {
            begin = 0;
            while(begin < end) {
                lists[begin] = merge(lists[begin], lists[end]);
                begin++, end--;
            }
        }
        return lists[0];
    }
    
    ListNode* merge(ListNode* p, ListNode* q) {
        if(p == NULL) return q;
        if(q == NULL) return p;
        
        ListNode* dummy = new ListNode(0);
        ListNode* tail = dummy;
        
        while(p && q) {
            if(p->val < q->val) {
                tail->next = p;
                p = p->next;
            }
            else {
                tail->next = q;
                q = q->next;
            }
            tail = tail->next;
        }
        tail->next = p ? p : q;
        tail = dummy->next;
        delete dummy;
        return tail;
    }
};