题解 | #合并k个已排序的链表#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    void shift(vector<ListNode *> &lists,int k,int m)//堆调整,注意这里层序编号和数组下标没有对应，需要减一后取元素
    {
        int i=k;
        int j=2*i;
        while(j<=m)
        {
            if(j<m&&lists[j-1]->val>lists[j-1+1]->val)//取左右孩子中较小者
            {
                ++j;
            }
            if(lists[j-1]->val>lists[i-1]->val)
            {
                break;
            }
            else
            {
                ListNode * temp=lists[j-1];
                lists[j-1]=lists[i-1];
                lists[i-1]=temp;

                i=j;
                j=2*i;
            } 
        }
    }
    int GetMinFromK(vector<ListNode *> &lists)
    {
        int m=lists.size();
        for(int i=0;i<m;++i)//把空链表放到数组后边
        {
            if(lists[i]==nullptr)
            {
                --m;
                swap(lists[i],lists[m]);

                --i;//不移动指针，继续判断是否为空
            }
        }
        if(m==0||m==1)//全是空元素,或者只有一个元素直接返回
        {
            return 0;
        }
        else 
        {
            for (int j=m/2;j>=1;j-- ) //建堆
            {
                shift(lists,j,m);
            }

            return 0;
        }
        
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode * virtualHead=new ListNode(-1);
        ListNode * aim=virtualHead;
        if(lists.size()==0)
        {
            return nullptr;
        }


        int index=GetMinFromK(lists);
        while(lists[index]!=nullptr )
        {
            aim->next=lists[index];//连接
            lists[index]=lists[index]->next;//更新表头
            aim=aim->next;

            int index=GetMinFromK(lists);
        }
        aim->next=nullptr;

        return virtualHead->next;

    }
};

可以使用与合并两个链表类似的方法进行，不过现在用从K个元素(未知个元素）中选取最小元素，无法使用if else选取

而应该选用排序算法，由于要求复杂为，假设k==n,那么每次选取出一个最大元素的复杂度应该为

,此处选用堆排序。

下面对程序中的代码作出解释

1.void shift(vector<ListNode *> &lists,int k,int m) 堆调整函数

2.int GetMinFromK(vector<ListNode *> &lists) 先将空表头尽量放在vector后面，必要时建立小根堆，并返回最小表头， 或者空指针在vector中的索引

3.main() 不断连接通过调用GetMinFromK(vector<ListNode *> &lists)得到最小元素为一个链表，更新Vector中的表头

注意：此题算然涉及到链表与排序，但是实际不是在为链表排序，而是对Vector容器中的元素排序