23.合并K个升序链表

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int listsSize=lists.size();
        //ListNode* head=nullptr;
        
        if(listsSize==0)                                            //空vector
            return nullptr;

        while(listsSize>1)
        {
            for(int i=0;i<listsSize;i+=1)
            {
                if(i+1==listsSize)                                  //奇数个list
                {
                    lists[i/2]=lists[i];
                    break;
                }
                else
                {
                    lists[i/2]=mergeTwoLists(lists[i],lists[i+1]);       
                    i+=1;
                }
            }
            listsSize=(listsSize+1)/2;                              
        }

        return lists[0];
        /*
        for(int i=0;i<listsSize;i++)                                //一个一个合并
        {
            head=mergeTwoLists(head,lists[i]);
        }
        
        return head;
        */
    }

    ListNode* mergeTwoLists(ListNode* & list1, ListNode* & list2)
    {
        ListNode *p1=list1, *p2=list2;
        ListNode *head,*t;

        if(list1==nullptr)return list2;                             
        if(list2==nullptr)return list1;

        if(p1->val<=p2->val)
        {
            head=p1;
            t=p1;
            p1=p1->next;
        }
        else
        {
            head=p2;
            t=p2;
            p2=p2->next;
        }
        
        while(p1!=nullptr||p2!=nullptr)
        {
            if(p2==nullptr)
            {
                t->next=p1;
                t=t->next;
                p1=p1->next;
            }           
            else if(p1==nullptr)
            {
                t->next=p2;
                t=t->next;
                p2=p2->next;
            }
            else if(p1->val<=p2->val)
            {
                t->next=p1;
                t=t->next;
                p1=p1->next;
            }
            else if(p1->val>p2->val)
            {
                t->next=p2;
                t=t->next;
                p2=p2->next;
            }
        }
        return head;
    }
};