LeetCode

leetcode 23. Merge k Sorted Lists 题解

查阅更多的题解,请点击 Github传送门

Problem

merge k sorted lists

Solution

设最长链表长度为n

heap, O(nlog(k)), O(1) space

观察问题,每次从k个节点中选出一个最小节点,加入新链表中,然后再加入一个节点,重复上述过程。过程中有以下特点:

  • k个节点“有序”,可以快速得到最小值
  • 加入新的节点,能快速恢复上述“有序”状态

小根堆刚好满足上述特点,其插入新元素的过程是O(logk),而O(nlogk)是时间复杂度的上界,实际的复杂度会更小。

class Solution
{
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        auto head = new ListNode(0);
        auto node = head;
        vector<ListNode *> minHeap;
        for (auto item : lists)
        {
            if (item != nullptr)
                minHeap.emplace_back(item);
        }
        make_heap(minHeap.begin(), minHeap.end(), mycompare);
        while (!minHeap.empty())
        {
            node->next = minHeap.front();
            node = node->next;
            auto next = minHeap.front()->next;
            node->next = nullptr;
            pop_heap(minHeap.begin(), minHeap.end(), mycompare);
            minHeap.pop_back();
            if (next != nullptr)
            {
                minHeap.push_back(next);
                push_heap(minHeap.begin(), minHeap.end(), mycompare);
            }
        }
        return head->next;
    }
};


divided and conquer

观察问题的老套路,问题是否可以分解(参照算法笔记(一)概述):merge 2个有序链表的问题是为人所熟知的,那么可以把merge k个有序链表的问题,分解成merge 2个有序链表的问题。

class Solution
{
    private:
    ListNode* mergeTwoLists(ListNode* root1,ListNode* root2){
        if(root1==nullptr||root2==nullptr)
            return root1 == nullptr ? root2 : root1;
        auto root = new ListNode(0);
        auto node = root;
        while (root1 != nullptr && root2 != nullptr)
        {
            if(root1->val<root2->val){
                node->next = root1;
                node = node->next;
                root1 = root1->next;
            }else{
                node->next = root2;
                node=node->next;
                root2 = root2->next;
            }
        }
        node->next = root1 == nullptr ? root2 : root1;
        return root->next;
    }

public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        ListNode* head = nullptr;
        for(auto item:lists){
            head = mergeTwoLists(head, item);
        }
        return head;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注