Merge k Sorted Lists 48ms use heap C++


  • 0
    S
    struct Heap {
        vector<ListNode*> vec;
        void push(ListNode * node);
        ListNode* pop();
    };
    
    void Heap::push(ListNode *node)
    {
        // 上浮
        vec.push_back(node);
        int down = vec.size() - 1;
        int up = (down - 1) / 2;
        while(up >= 0 && vec[down]->val < vec[up]->val)
        {
            swap(vec[up], vec[down]);
            down = up;
            up = (down - 1) / 2;
        }
        
    }
    
    ListNode* Heap::pop()
    {
        ListNode *ret = vec[0];
        // 下滤
        ListNode *temp = vec.back();
        vec.pop_back();
        size_t size = vec.size();
        int up = 0;
        int down = 2 * up + 1;
        while(down < size)
        {
            if(down+1 < size && vec[down]->val > vec[down+1]->val)
                down++;
            if(vec[down]->val >= temp->val)
                break;
            vec[up] = vec[down];
            up = down;
            down = 2 * up + 1;
        }
        vec[up] = temp;
        return ret;
    }
     
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            ListNode dummy(0);
            ListNode *head = &dummy;
            Heap heap;
            int i = 0;
            int count = 100;
            while(count--)
            {
                for(int i = 0; i < lists.size(); ++i)
                {
                    auto iter = lists[i];
                    if(!iter)
                        continue;
                    heap.push(iter);
                    iter = iter->next;
                    lists[i] = iter;
                }
            }
            
            bool flag = true;
            while(flag) {
                i = 0;
                flag = false;
                for(int i = 0; i < lists.size(); ++i)
                {
                    auto iter = lists[i];
                    if(iter)
                        flag = true;
                    else
                        continue;
                    head->next = heap.pop();
                    head = head->next;
                    heap.push(iter);
                    iter = iter->next;
                    lists[i] = iter;
                }
            }
            
            while(heap.vec.size()) {
                head->next = heap.pop();
                head = head->next;
            }
            head->next = nullptr;
            return dummy.next;
        }
    
    };

Log in to reply
 

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