[recommend for beginners]clean C++ implementation with detailed explanation


  • 6

    There are 2 ways to merge all the #lists linked-list:

    -1- we can merge the lists[0] with the lists[i] additively and record the results with the cur-pointer

    -2- we can merge the top of the linked-lists and push the merged-linked-lists to the tail of the vector.

    I can not figure out why the method-1- have TLE problem while the method-2- is OK ?

    Solution:

     because the method-1- merge-one-list-one-time, but the method-2- merge-2-list-one-time
    

    Here is my implementation:

       class Solution {
        public:
            ListNode* mergeKLists(vector<ListNode*>& lists) {
                //merge way -1-
                if(lists.empty())   return NULL;
                ListNode* cur=lists[0];
                cout<<lists.size()<<endl;
                for(int i=1; i<lists.size(); i++){
                    cur=mergeTwoLists(cur, lists[i]);
                }
                return cur;
                
                //merge way -2-
                if(lists.empty()){
                    return nullptr;
                }
                while(lists.size() > 1){
                    lists.push_back(mergeTwoLists(lists[0], lists[1]));
                    lists.erase(lists.begin());
                    lists.erase(lists.begin());
                }
                return lists.front();
            }
         
            
            ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
                ListNode* dummy=new ListNode(-1);
                ListNode* cur=dummy;
                while(l1 && l2){
                    if(l1->val < l2->val){
                        cur->next=l1;
                        cur=l1;
                        l1=l1->next;
                    }
                    else{
                        cur->next=l2;
                        cur=l2;
                        l2=l2->next;
                    }
                }
                if(!l1)  cur->next=l2;
                if(!l2)  cur->next=l1;
                return dummy->next;
            }
        };

  • 0

    Priority-heap-implementation

       class Solution {
            struct compare{
                bool operator()(const ListNode* l, const ListNode* r){
                    return l->val > r->val;
                }
            };
        public:
            ListNode* mergeKLists(vector<ListNode*>& lists) {
                int k=lists.size();
                priority_queue<ListNode*, vector<ListNode*>, compare> q;
                /*** construct min-heap-from-all-lists ***/
                for(auto l : lists){
                    if(l)  q.push(l);
                }
                if(q.empty())   return NULL;
                /*** get-the-head-of-the-final-result-linked-list ***/
                ListNode* result=q.top();
                q.pop();
                if(result->next) q.push(result->next);
                ListNode* tail=result;
                while(!q.empty()){
                    tail->next=q.top();
                    q.pop();
                    tail=tail->next;
                    if(tail->next) q.push(tail->next);
                }
                return result;
            }
        };

  • 1

    Here is the official example, we can know that the insert and delete option related to make_heap()

    delete element:

     pop_heap()     v.pop_back()
    

    insert element

    v.push_back()      push_heap();
    

    sort element

     sort_heap()
    

    Here is the code

     // range heap example
    #include <iostream>     // std::cout
    #include <algorithm>    // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
    #include <vector>       // std::vector
    
    int main () {
      int myints[] = {10,20,30,5,15};
      std::vector<int> v(myints,myints+5);
    
      std::make_heap (v.begin(),v.end());
      std::cout << "initial max heap   : " << v.front() << '\n';
    
      std::pop_heap (v.begin(),v.end()); v.pop_back();
      std::cout << "max heap after pop : " << v.front() << '\n';
    
      v.push_back(99); std::push_heap (v.begin(),v.end());
      std::cout << "max heap after push: " << v.front() << '\n';
    
      std::sort_heap (v.begin(),v.end());
    
      std::cout << "final sorted range :";
      for (unsigned i=0; i<v.size(); i++)
        std::cout << ' ' << v[i];
    
      std::cout << '\n';
    
      return 0;
    }
    

    Here is the make_heap based solution

       class Solution {
            static bool heapComp(ListNode* a, ListNode* b){
                return a->val > b->val;
            }
        public:
            ListNode* mergeKLists(vector<ListNode*>& lists) {
                ListNode head(0);
                ListNode *cur=&head;
                vector<ListNode*> v;
                for(int i=0; i<lists.size(); i++){
                    if(lists[i])  v.push_back(lists[i]);
                }
                make_heap(v.begin(), v.end(), heapComp);
                while(v.size()>0){
                    cur->next=v.front();
                    pop_heap(v.begin(), v.end(), heapComp);
                    v.pop_back();
                    cur=cur->next;
                    if(cur->next){
                        v.push_back(cur->next);
                        push_heap(v.begin(), v.end(), heapComp);
                    }
                }
                return head.next;
            }
        };
    

  • 1
    L

    IMHO, method-1 and method-2 both decrease one list one time. The reason why method-2 is better is that method-2 probably merge two lists of similar length, while method-1 doesn't.

    Consider the following example:
    [[5],[4],[3],[2],[1]]

    method-1: compare times

    [[1,5],[4],[3],[2]] 1

    [[1,2,5],[4],[3]] 2

    [[1,2,3,5],[4]] 3

    [[1,2,3,4,5]] 4

    total 10 compare times

    method-2: compare times

    [[3],[2],[1],[4,5]] 1

    [[1],[4,5],[2,3]] 1

    [[2,3],[1,4,5]] 1

    [[1,2,3,4,5]] 3

    total 6 compare times


  • 0
    class Compare {
        public:
        bool operator() (const ListNode* a, const ListNode* b)
        {
            return a->val > b->val;
        }
    };
    class Solution {
    
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            int k = lists.size();
            priority_queue<ListNode*, vector<ListNode*>, Compare>  q;
            for (auto it : lists) {
                if (it)  q.push(it);
            }
            ListNode* dummy = new ListNode(-1);
            ListNode* tail = dummy;
            
            while (!q.empty()) {
                tail->next = q.top();
                q.pop();
                tail = tail->next;
                if (tail->next) q.push(tail->next);
            }
            return dummy->next;
        }
    };

  • 1
    L

    said in [recommend for beginners]clean C++ implementation with detailed explanation:

        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode* dummy=new ListNode(-1);
            ListNode* cur=dummy;
    

    I think to create a dummy node, instead of using new key word, probably just create a node object is better, to avoid memory leak.
    [original]
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy=new ListNode(-1);
    ListNode* cur=dummy;

    [modified]
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(-1);
    ListNode* cur=&dummy;

    In this way, when the sub-function returns, the memory will be automatically released.


Log in to reply
 

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