LeetCode 23 Merge k Sorted Lists

    
        标签：
        
            链表问题
        
            LeetCode
        
    发布于：2022-02-05 15:14:05
    编辑于：2022-02-05 16:51:58
    浏览量：802

题目分析

https://leetcode.com/problems/merge-k-sorted-lists/ k 个链表，设 n 为每个链表的元素个数。

直接法

第一次的时候排序各个链表的首节点，之后只取最小值，然后新的值未必是最小的，冒泡到其目标位置。

我们需要处理 nk 个节点，每个节点的冒泡如果用二分搜索寻找合适位置的话复杂度 O(logk)，插入本身则要 O(k)，最终的时间复杂度为 O(nk^2)。

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // remove all nullptr in the lists
        auto it = lists.begin();
        while (it != lists.end()) {
            if (*it == nullptr) {
                it = lists.erase(it);
            } else {
                ++it;
            }
        }
        if (lists.size() == 0) return nullptr;

        sort(begin(lists), end(lists), [](const auto &lhs, const auto &rhs) {
            return lhs->val < rhs->val;
        });
        ListNode head;
        ListNode *tail = &head;
        while (true) {
            tail->next = lists[0];
            tail = tail->next;

            lists[0] = lists[0]->next;
            if (lists[0] == nullptr) {
                lists.erase(lists.begin());
                if (lists.empty()) break;
            }

            // Find a proper position for cur.
            int i = 1;
            for (; i < lists.size(); i++) {
                if (lists[0]->val <= lists[i]->val) {
                    break;
                }
            }
            lists.insert(lists.begin() + i, lists[0]);
            lists.erase(lists.begin());
            // move(lists, 0, i-1);
        }
        return head.next;
    }
};

直接法（维护两个排序数组）

维护两个排序数组，第一次的时候排序各个链表的首节点，作为第一个排序数组；之后只取最小值，然后新的值放到两个排序数组中元素个数较小的那个。

也就是说，每次新的值我们需要跟两个数组的最小值进行比较：

其是最小的，那直接拼接它就好了。
其不是最小的，返回两个数组的末尾值中较小的那个，然后把新值插入到排序数组的合适位置。

同样需要处理 nk 个节点，两个数组的平均长度为 k，寻找合适位置的话复杂度 O(logk)，插入本身则要 O(k)，最终的时间复杂度也为 O(nk^2)。

嗯，相比上一个方法并不划算啊喂！

递归法

两两合并列表，最后合并成一个已排序数组。 k 个链表，则我们需要操作 k 次，每次的复杂度为 O(n)，但是这里的 n 会越来越大，所以最终的时间复杂度不是 O(kn)，而是 O(kn^2)。

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return nullptr;
        vector<ListNode*> temp;
        while (lists.size() > 1) {
            for (int i = 0; i < lists.size(); i += 2) {
                if (i + 1 < lists.size()) {
                    temp.push_back(mergeTwoLists(lists[i], lists[i+1]));
                } else {
                    temp.push_back(lists[i]);
                }
            }
            lists = temp;
            temp.clear();
        }
        return lists[0];
    }
    
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode head;
        ListNode* c = &head;
        while (list1 && list2) {
            if (list1->val < list2->val) {
                c->next = list1;
                list1 = list1->next;
            } else {
                c->next = list2;
                list2 = list2->next;
            }
            c = c->next;
        }
        c->next = list1 ? list1 : list2;
        return head.next;
    }
};

优先级队列

https://labuladong.gitee.io/algo/2/17/16/#合并-k-个有序链表

优先级队列适合处理这种只需要极值的情况。

每个元素都要入和出，一共 mk 个元素，堆的尺寸为 k，则时间复杂度为 O(mklogk)

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto comp = [](ListNode* a, ListNode* b) {
          return a->val > b->val;  
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> pq(comp);
        for (auto list : lists) {
            if (list) {
                pq.push(list);
            }
        }
        ListNode head;
        auto c = &head;
        while (!pq.empty()) {
            c->next = pq.top();
            pq.pop();
            if (c->next->next) {
                pq.push(c->next->next);
            }
            c = c->next;
        }
        return head.next;
    }
};

Links: leetcode-23-merge-k-sorted-lists