Concise C++ solution using std::priority_queue


  • 1
    S

    It took 48ms. Could be faster if adding a few lines to take care of the empty lists thus avoiding from the first two if-statements in the loop.

    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            priority_queue<ListNode*, vector<ListNode*>, bool(*)(ListNode*, ListNode*)> listq(comp, lists);
            ListNode *head = nullptr, *tail, *top;
            while (!listq.empty()) {
                top = listq.top();
                listq.pop();
                if (top == nullptr)
                    continue;
                if (head == nullptr) {
                    head = new ListNode(top->val);
                    tail = head;
                } else {
                    tail->next = new ListNode(top->val);
                    tail = tail->next;
                }
                if (top->next != nullptr)
                    listq.push(top->next);
            }
            return head;
        }
    
    private:
        static bool comp(ListNode *a, ListNode *b) { 
            return (a == nullptr || b == nullptr) ? (b != nullptr) : (a->val > b->val);
        }
    };

Log in to reply
 

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