2022-12-23发表2023-08-03更新算法4 分钟读完 (大约634个字)0次访问

LeetCode.23 合并K个升序链表

记录了一道使用多种方法合并K个升序链表的问题。

顺序合并

按顺序两两进行合并。代码如下：

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *p = nullptr;
        for (auto l : lists) p = mergeTwoLists(p, l);
        return p;
    }

    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy, *p1 = l1, *p2 = l2;
        while (p1 && p2) {
            if (p1->val <= p2->val) {
                p->next = p1;
                p1 = p1->next;
            }
            else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        p->next = p1 ? p1 : p2;
        return dummy->next;
    }
};

时间复杂度：$O(k^2n)$，其中$k$为链表的个数，$n$为链表的长度。
空间复杂度：$O(1)$

分治法

类似于归并排序，第一轮先合并$\frac{k}{2}$组（每组两个链表），第二轮合并$\frac{k}{2^2}$组，以此类推，最后一轮合并最后一组（$\frac{k}{2^{\log k}}$)。代码如下：

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

    ListNode* merge(vector<ListNode*>& lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = l + r >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy, *p1 = l1, *p2 = l2;
        while (p1 && p2) {
            if (p1->val <= p2->val) {
                p->next = p1;
                p1 = p1->next;
            }
            else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        p->next = p1 ? p1 : p2;
        return dummy->next;
    }
};

时间复杂度：$O(kn\log k)$，即，第一轮合并$\frac{k}{2}$组，每组时间代价为$2n$，所以第一轮时间代价为$kn$；第二轮合并$\frac{k}{2^2}$组，每组时间代价为$2^2n$，所以第二轮时间代价也为$kn$，以此类推，共有$\log k$轮，总时间代价为$kn\log k$。
空间复杂度：$O(\log k)$，递归的栈空间。

堆（优先队列）

将每个链表没有被合并的元素的最前面一个放入小根堆中，$k$个链表堆中最多有$k$个元素，每次将堆顶的元素弹出合并，再将该链表的下一个元素放入。代码如下：

struct Element {
    int val;
    ListNode *ptr;
    bool operator< (const Element &rhs) const {
        return val > rhs.val;
    }
};

class Solution {
public:
    priority_queue<Element> heap;
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto list : lists) {
            if (list) heap.push({list->val, list});
        }
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy;
        while (!heap.empty()) {
            auto t = heap.top(); heap.pop();
            p->next = t.ptr;
            p = p->next;
            if (t.ptr->next) heap.push({t.ptr->next->val, t.ptr->next});
        }
        return dummy->next;
    }
};