題目: LeetCode - 23. Merge k Sorted Lists
題目說明
給 k 個已經由小到大排序好的 Lists,將全部合成一個由小到大排序的 List。
解題思路
使用 priority_queue 幫我們排序,由於是自定義的型態,所以需要自己寫比較函數。先遍歷一次 lists
將所有 list 的 head 都推入,接著將 pq.top()
連接,若 pq.top()->next
存在,就重新推入。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { auto cmp = [](ListNode* l, ListNode* r) { return l->val > r->val; }; priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp); auto head = new ListNode(), tail = head; for(auto& ptr : lists) if(ptr) pq.push(ptr); while(!pq.empty()) { tail->next = pq.top(), tail = tail->next, pq.pop(); if(tail->next) pq.push(tail->next); } return head->next; } };
|