学步园

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

算法一，自底至顶递归。

时间复杂度为O(nlogk)。

空间复杂度为O(k)。

此算法在leetcode上实际执行时间为 144ms (130 test cases)。

/**
 * 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 0;
        if (lists.size() == 1) return lists.back();

        vector<ListNode *> l;
        while (!lists.empty()) {
                if (lists.size() == 1) {
                        l.push_back(lists.back());
                        lists.pop_back();
                }
                else {
                        ListNode *p = lists.back();
                        lists.pop_back();
                        ListNode *q = lists.back();
                        lists.pop_back();

                        l.push_back(merge(p, q));
                }
        }

        return mergeKLists(l);
    }

    ListNode *merge(ListNode *p,ListNode *q) {
        ListNode fake(0);
        ListNode *m = &fake;

        while (p && q) {
                if (p->val < q->val) {
                        m->next = p;
                        p = p->next;
                }
                else {
                        m->next = q;
                        q = q->next;
                }
                m = m->next;
        }

        m->next  = p ? p : q;
        return fake.next;
    }
};

算法二，自顶向下分而治之进行递归

此算法在leetcode上实际执行时间为136ms。

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
       return mergeKLists(lists, 0, lists.size());
    }


    ListNode *mergeKLists(vector<ListNode *> &lists, size_t start, size_t stop) {
        if (stop <= start) return 0;
        if (stop == start+1) return lists[start];

        const size_t mid = (start + stop) / 2;
        return merge(mergeKLists(lists, start, mid), mergeKLists(lists, mid, stop));
    }

    ListNode *merge(ListNode *p,ListNode *q) {
        ListNode fake(0);
        ListNode *m = &fake;

        while (p && q) {
                if (p->val < q->val) {
                        m->next = p;
                        p = p->next;
                }
                else {
                        m->next = q;
                        q = q->next;
                }
                m = m->next;
        }

        m->next  = p ? p : q;
        return fake.next;
    }
};

算法3:利用优先队列

此算法在leetcode上实际执行时间为216ms。

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode *, vector<ListNode *>, comparison> pqueue;
        while (!lists.empty()) {
                if (lists.back())
                        pqueue.push(lists.back());

                lists.pop_back();
        }

        ListNode fake(0);
        ListNode *p = &fake;
        while (!pqueue.empty()) {
                p->next = pqueue.top();
                p = p->next;
                pqueue.pop();
                if (p->next) {
                        pqueue.push(p->next);
                }
        }
        return fake.next;
    }

    struct comparison {
        bool operator() (ListNode *lhs, ListNode *rhs) const {
                return lhs->val > rhs->val;
        }
    };
};