K個の並べ替えられたチェーンテーブルをマージします.ソートチェーンテーブルを返します

本題はLeetCodeに由来する
-------------------------------------------------------------
考え方1:優先キュー
1すべてのチェーンテーブルを巡回し、最初のノードを優先キューに入れます.
2優先キューのヘッダ、すなわち最小ノードを取り出す.新しいチェーンテーブルの末尾にリンクします.
3キューヘッダノードのチェーンテーブルが空でない場合は、次のノードをキューに入れます.手順1～3を順に繰り返します.
コード:

  struct compare{
        bool operator()(const ListNode* a,const ListNode* b){
            return a->val > b->val;
        }
    };
public:
    ListNode *mergeKLists(vector &lists) {
        priority_queue,compare> que;  //    
        for(auto node:lists){
            if(node)
            	que.push(node);
        }
        if(que.empty())
            return NULL;
        ListNode* root=new ListNode(0);
        root->next=NULL;
        ListNode* pre=root;
        while(que.size()){
            ListNode* p=que.top();    //     ，       
            que.pop();
            pre->next=p;
            pre=p;
            if(pre->next){           //         ，    
                que.push(pre->next);
            }
        }
        return root->next;
    }

考え方2:最小ヒープ
1上記と同様に各チェーンテーブルの先頭ノードを巡回してスタックを構築する
2ヒープの頂点を取り出し、ヒープを調整する
3現在の最小ノードのチェーンテーブルが空でない場合、次のノードはスタックに入り、スタックを調整し、ループします.
コード:

    struct compare{
        bool operator()(const ListNode* a,const ListNode* b){
            return a->val > b->val;
        }
    };
public:
    ListNode *mergeKLists(vector &lists) {
        vector vec;    //   
        for(auto node:lists){
            if(node)
                vec.push_back(node);
        }
        ListNode* root=new ListNode(0);
        root->next=NULL;
        ListNode* pre=root;
        make_heap(vec.begin(),vec.end(),compare());   //  
        while(vec.size()){
            pre->next=vec[0];
            pop_heap(vec.begin(),vec.end(),compare());   //              
            vec.pop_back();  //        
            pre=pre->next;
            if(pre->next){
                vec.push_back(pre->next);
                push_heap(vec.begin(),vec.end(),compare());
            }
        }
        return root->next;
        
    }

考え方3
集計ソート.まず2つを合併してから合併します
コード:

 ListNode *mergeKLists(vector &lists) {
        if(lists.size()==0)
            return NULL;
        while(lists.size()>1){
            lists.push_back(mergeList(lists[0],lists[1]));
            lists.erase(lists.begin());
            lists.erase(lists.begin());
        }
        return lists.front();
    }
    ListNode* mergeList(ListNode* l1,ListNode* l2){
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        if(l1->valval){
            l1->next=mergeList(l1->next,l2);
            return l1;
        }else{
            l2->next=mergeList(l1,l2->next);
            return l2;
        }
    }