A c++ solution using std::multiset


  • 0
    L

    create a multiset storing head pointers of each set:)

    struct Comp {
        bool operator() (const ListNode* l1, const ListNode* l2) {
            return l1->val < l2->val;
        }
    };
    
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            ListNode *preHead = new ListNode(0);
            ListNode *it = preHead;
            multiset<ListNode*, Comp> listSet;
            for (ListNode* &list : lists) {
                if (list != NULL)
                    listSet.insert(list);
            }
            
            while (!listSet.empty()) {
                auto minOne = listSet.begin();
                it->next = new ListNode((*minOne)->val);
                it = it->next;
                ListNode* toAdd = (*minOne)->next;
                listSet.erase(minOne);
                if (toAdd)
                    listSet.insert(toAdd);
            }
            return preHead->next;
        }
    };

Log in to reply
 

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