My solution based on priority_queue (with some questions)


  • 0
    0

    The general idea of this problem to find the node with the least value and append to one linked list.
    But how to find the minimal value quickly? I use a priority queue (heap) the save all the head node of lists (which is not null).
    So the top of the heap is the minimal node, then append it to the result linked list and push the node->next into the heap, until the heap is empty.

    But the heap cannot save ListNode *. I have to new ListNode() to append node to linked list, which may waste memory. How can I solve it?

    Thanks

    // reload the operator to make the min heap
    bool operator< (ListNode a, ListNode b){
        return a.val > b.val;
    };
    
    class Solution {
    public:
    
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            ListNode* head = new ListNode(0);
            ListNode* p = head;
            priority_queue<ListNode> q;
            for (vector<ListNode *>::iterator it = lists.begin(); it != lists.end(); ++it) {
                if (*it != NULL) {
                    q.push(**it);  // push heads of lists
                }
            }
            while (!q.empty()) {
                ListNode n = q.top();
                q.pop();
                p->next = new ListNode(n.val);
                p = p->next;
                if (n.next != NULL) {
                    q.push(*(n.next));
                }
            }
            return head->next;
        }
    
    };

Log in to reply
 

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