My simple C++ solution with heap


  • 0
    W
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        static bool cmp(ListNode* a, ListNode* b) {
            return a->val > b->val;
        }
        
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            int len = (int)lists.size();
            for (int i=0; i<len; i++) {
                if (lists[i] == NULL) {
                    lists.erase(lists.begin() + i);
                    i--;
                    len--;
                }
            }
            ListNode* head = new ListNode(0);
            ListNode* p = head;
            make_heap(lists.begin(), lists.end(), cmp);
            
            while (!lists.empty()) {
                p->next = lists.front();
                if (lists.front()->next == NULL) {
                    pop_heap(lists.begin(), lists.end(), cmp);
                    lists.pop_back();
                } else {
                    lists.front() = lists.front()->next;
                    pop_heap(lists.begin(), lists.end(), cmp);
                    push_heap(lists.begin(), lists.end(), cmp);
                }
                p = p->next;
            }
            
            return head->next;
        }
    };
    

Log in to reply
 

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