class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* rhead = nullptr;//定義合并后鏈表的頭節(jié)點(diǎn)
        ListNode* rtail = nullptr;//定義合并后鏈表的尾結(jié)點(diǎn)
        while (true)
        {
            int minIndex = -1;//定義lists數(shù)組中最小節(jié)點(diǎn)下標(biāo)，最初等于-1，（下簡稱最小位置）
            int i = lists.size();//
            while (i--)
            {
                if (lists[i] != nullptr)//首先判斷數(shù)組當(dāng)前位置的節(jié)點(diǎn)是否為空
                {
                    //當(dāng)前節(jié)點(diǎn)不為空再進(jìn)來
                    if (minIndex == -1)//判斷最小位置是否是-1，如果是就直接把當(dāng)前位置賦值給minIndex
                    {
                        minIndex = i;
                    }
                    else if (lists[i]->val < lists[minIndex]->val)//如果minIndex不為-1，則用數(shù)組當(dāng)前位置節(jié)點(diǎn)的val與記錄的最小位置上節(jié)點(diǎn)的val進(jìn)行比較
                    {
                        minIndex = i;//如果當(dāng)前節(jié)點(diǎn)的val值更小，那就更新minIndex
                    }
                }
            }
            if (minIndex == -1)//遍歷完一遍數(shù)組如果minIndex的值還是-1，說明當(dāng)前數(shù)組中的所有節(jié)點(diǎn)全是空
            {
                return rhead;//此時(shí)說明所有鏈表已經(jīng)合并完成，可以返回頭節(jié)點(diǎn)
            }
            if (rhead == nullptr)//確定新鏈表的頭節(jié)點(diǎn)
            {
                rhead = rtail = lists[minIndex];
            }
            else//之后每找出一個(gè)最小的節(jié)點(diǎn)，進(jìn)行尾插即可
            {
                rtail->next = lists[minIndex];
                rtail = rtail->next;
            }
            lists[minIndex] = lists[minIndex]->next;//最小的節(jié)點(diǎn)已經(jīng)尾插到新鏈表，因此要對最小位置上的節(jié)點(diǎn)更新
        }
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return dividemerge(lists, 0, lists.size() - 1);
    }
private:
    ListNode* dividemerge(vector<ListNode*>& lists, int left, int right)
    {
        if (left > right)
        {
            return nullptr;
        }
        else if (left == right)
        {
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        //分治
        ListNode* head1 = dividemerge(lists, left, mid);
        ListNode* head2 = dividemerge(lists, mid + 1, right);
        //對子問題處理
        return Merge(head1, head2);
    }
private:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)//合并兩個(gè)有序鏈表
    {
        if (pHead1 == nullptr)
        {
            return pHead2;
        }
        if (pHead2 == nullptr)
        {
            return pHead1;
        }
        ListNode* pHeadret, * tail;
        if (pHead1->val < pHead2->val)
        {
            pHeadret = tail = pHead1;
            pHead1 = pHead1->next;
        }
        else
        {
            pHeadret = tail = pHead2;
            pHead2 = pHead2->next;
        }
        while (pHead1 != nullptr && pHead2 != nullptr)
        {
            if (pHead1->val < pHead2->val)
            {
                tail->next = pHead1;
                pHead1 = pHead1->next;
            }
            else
            {
                tail->next = pHead2;
                pHead2 = pHead2->next;
            }
            tail = tail->next;
        }
        if (pHead2 != nullptr)
        {
            tail->next = pHead2;
        }
        if (pHead1 != nullptr)
        {
            tail->next = pHead1;
        }
        return pHeadret;
    }
};

//分治
ListNode* head1 = dividemerge(lists, left, mid);        
ListNode* head2 = dividemerge(lists, mid + 1, right);

//對子問題處理        
return Merge(head1, head2);