class Solution {
    #ifdef _commet
    k路归并两种做法，一种是转化成两路归并，一种是用小顶堆来做，两种都是O（nlogk）
    #endif
public:
    #ifdef _heap
    struct heapCmp{
        bool operator() (ListNode* a,ListNode *b)
        {
            return a->val > b->val; 
        } 
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode *,vector<ListNode *>, heapCmp> heap;
        auto ans = new ListNode(-1),tail = ans;
        for(auto l:lists)
            if(l)
                heap.push(l);
        while(!heap.empty())
        {
            auto tmp = heap.top();
            heap.pop();
            tail = tail->next = tmp;
            if(tail->next)//注意要判断next是否为空 否则会runtime error
                heap.push(tail->next);
        }
        return ans->next;
    }
    #endif
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)//注意函数形参为ListNode*而不是vector<ListNode*>
    {
        auto ans=new ListNode(-1),tail=ans;
        while(l1!=NULL && l2!=NULL)
        {
            if(l1->val > l2->val)
            {
                tail = tail->next = l2;
                l2 = l2->next;
            }
            else
            {
                tail = tail->next = l1;
                l1 = l1->next;
            }
        }
        tail->next=l1!=NULL?l1:l2;
        return ans->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0)
            return NULL;
        if (lists.size() == 1)
            return lists[0];

        int mid= lists.size()/2;
        vector<ListNode*> k_left = vector<ListNode*>(lists.begin(),lists.begin()+mid);
        vector<ListNode*> k_right =vector<ListNode*>(lists.begin()+mid, lists.end());
        ListNode* l = mergeKLists(k_left);//通过递归函数本身将vector<ListNode *>转化成ListNode*求两路归并
        ListNode * r = mergeKLists(k_right);
        return mergeTwoLists(l,r);
    }

};