C++ solution based on priority queue


  • 1
    X
    class Solution {
    public:
        /**
         * @param lists: a list of ListNode
         * @return: The head of one sorted list.
         */
        struct cmp {  
            bool operator()(ListNode *a, ListNode *b) {  
                return a->val > b->val;
            }  
        };
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            ListNode *head = new ListNode(0), *tail = head;
            priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
            for (auto p : lists)
                if (p)
                    heap.push(p);
            while (!heap.empty()) {
                auto p = heap.top();
                heap.pop();
                if (p->next)
                    heap.push(p->next);
                tail->next = p;
                tail = tail->next;
            }
            return head->next;
        }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.