Merge k Sorted Lists

描述​

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

代码​

解法1: 直接调用 mergeTwoLists()​

// Merge k Sorted Lists// 时间复杂度O(N)，空间复杂度O(1)public class Solution {    public ListNode mergeKLists(ListNode[] lists) {        if (lists.length == 0) return null;        ListNode p = lists[0];        for (int i = 1; i < lists.length; i++) {            p = mergeTwoLists(p, lists[i]);        }        return p;    }    // Merge Two Sorted Lists    ListNode mergeTwoLists(ListNode l1, ListNode l2) {        ListNode head = new ListNode(-1);        for (ListNode p = head; l1 != null || l2 != null; p = p.next) {            int val1 = l1 == null ? Integer.MAX_VALUE : l1.val;            int val2 = l2 == null ? Integer.MAX_VALUE : l2.val;            if (val1 <= val2) {                p.next = l1;                l1 = l1.next;            } else {                p.next = l2;                l2 = l2.next;            }        }        return head.next;    }}

解法2: 两两调用 mergeTwoLists()​

• 第1次循环中，k个链表个数减半，共调用了 k/2mergeTwoLists()，每次mergeTwoLists()时间复杂度为N/k，因此总时间复杂度为 $k/2 * N/k=N/2$
• 第2次循环中，链表个数继续减半，变为 k/4，共调用了 k/4mergeTwoLists()，每次mergeTwoLists()时间复杂度为2N/k，因为上一轮把每条单链表的长度边长了，因此总时间复杂度为 $k/4 \times 2N/k=N/2$
• 依此类推，第$\log{k}$次循环的时间复杂度为 $k/{2^{\log{k}}} \times 2^{\log{k}-1} \times N/k=N/2$

// Merge k Sorted Lists// 时间复杂度O(logk*N/2)，空间复杂度O(1)class Solution {public:    ListNode *mergeKLists(vector<ListNode *> &lists) {        if (lists.empty()) return nullptr;        while(lists.size() > 1){            lists.push_back(mergeTwoLists(lists[0], lists[1]));            lists.erase(lists.begin());            lists.erase(lists.begin());        }        return lists.front();    }    // Merge Two Sorted Lists    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {        ListNode head(-1);        for (ListNode* p = &head; l1 != nullptr || l2 != nullptr; p = p->next) {            int val1 = l1 == nullptr ? INT_MAX : l1->val;            int val2 = l2 == nullptr ? INT_MAX : l2->val;            if (val1 <= val2) {                p->next = l1;                l1 = l1->next;            } else {                p->next = l2;                l2 = l2->next;            }        }        return head.next;    }};

解法3: 小根堆​

// Merge k Sorted Lists// 时间复杂度O(Nlogk)，空间复杂度O(logk)struct compare {    bool operator()(const ListNode* l, const ListNode* r) {        return l->val > r->val;    }};class Solution {public:    ListNode *mergeKLists(vector<ListNode *> &lists) {        if(lists.empty()) return nullptr;        priority_queue<ListNode* , vector<ListNode *>, compare> pq;        for (auto i : lists) {            if(i) pq.push(i);        }        ListNode * dummy = new ListNode(-1);        ListNode * tail =  dummy;        while (!pq.empty()) {            tail->next = pq.top();            tail = tail->next;            pq.pop();            if(tail->next) {                pq.push(tail->next);            }        }        return dummy->next;    }};