{"id":2542,"date":"2018-04-29T15:37:05","date_gmt":"2018-04-29T07:37:05","guid":{"rendered":"https:\/\/boweihe.me\/?p=2542"},"modified":"2018-04-29T15:37:05","modified_gmt":"2018-04-29T07:37:05","slug":"leetcode-23-merge-k-sorted-lists","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2542","title":{"rendered":"LeetCode 23. Merge k Sorted Lists"},"content":{"rendered":"<p>https:\/\/leetcode.com\/problems\/merge-k-sorted-lists\/description\/<br \/>\nUse max heap, the time complexity is O( log(k) * N )<\/p>\n<pre class=\"theme:github lang:c++ decode:true \">\/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode(int x) : val(x), next(NULL) {}\n * };\n *\/\nclass Solution {\npublic:\n    ListNode* mergeKLists(vector&lt;ListNode*&gt;&amp; lists) {\n        if (lists.empty())\n            return nullptr;\n        auto comparor = [](ListNode* lhs, ListNode* rhs) {\n            return lhs-&gt;val &gt; rhs-&gt;val;\n        };\n        priority_queue&lt;ListNode*, vector&lt;ListNode*&gt;, decltype(comparor)&gt; pri_queue(comparor);\n        \/\/ perpare queue with K items\n        for(auto&amp; list : lists)\n        {\n            if (list != nullptr)\n                pri_queue.push(list);\n        }\n        ListNode* head = new ListNode(-1);\n        ListNode* prev = head;\n        ListNode* current = nullptr;\n        while (!pri_queue.empty())\n        {\n            current = pri_queue.top();\n            prev-&gt;next = current;\n            ListNode* next = current-&gt;next;\n            pri_queue.pop();\n            if (next != nullptr)\n                pri_queue.push(next);\n            prev = current;\n        }\n        return head-&gt;next;\n    }\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode.com\/problems\/merge-k-sorted-lists\/description\/ Use max heap, the time complexity is O( log(k) * N ) \/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; *\/ class Solution { public: ListNode* mergeKLists(vector&lt;ListNode*&gt;&amp; lists) { if (lists.empty()) return nullptr; auto comparor = [](ListNode* [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[66],"class_list":["post-2542","post","type-post","status-publish","format-standard","hentry","category-technical","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2542","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2542"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2542\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2542"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2542"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2542"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}