两两排序法

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    //改变原两个链表的指针指向排成新链表 节省空间
    struct ListNode* H=malloc(sizeof(struct ListNode));
    struct ListNode* cur=H;
    while(pHead1!=NULL&&pHead2!=NULL)
    {
        if(pHead1->val<=pHead2->val)
        {
            cur->next=pHead1;
            cur=cur->next;
            pHead1=pHead1->next;
        }
        else
        {
            cur->next=pHead2;
            cur=cur->next;
            pHead2=pHead2->next;    
        }
    }
    //若是有一边链表未遍历完，可直接指向当前节点，原链表已排好序
    if(pHead1!=NULL)
    {
        cur->next=pHead1;
    }
    if(pHead2!=NULL)
    {
        cur->next=pHead2;
    }
    return H->next;
    // write code here
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    if(listsLen==0)
        return NULL;
    int i=0;
    while(1)
    {
        for(i=0;i<listsLen/2;i++)//将链表首尾互排直至中间
        {
            lists[i]=Merge(lists[i],lists[listsLen-i-1]);//排序链表迭代
        }
        if(listsLen==2)
            break;
        listsLen=listsLen%2==1?listsLen/2+1:listsLen/2;//对K为单双数的处理
        
    }
    return lists[0];
}

辅助数组快排法

int cmp(const void* a,const void* b)
{
    return *(int *)a-*(int *)b;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    struct ListNode* result=malloc(sizeof(struct ListNode));
    struct ListNode* cur;
    int j=0;
    int num[100000];
    for(int i=0;i<listsLen;i++)//遍历lists的所有节点存入num中
    {
        cur=lists[i];
        while(cur!=NULL)
        {
            num[j++]=cur->val;
            cur=cur->next;
        }
    }
    qsort(num, j,sizeof(int), cmp);//升序快排
    cur=result;
    for(int i=0;i<j;i++)//创建链表
    {
        struct ListNode* temp=malloc(sizeof(struct ListNode));
        temp->val=num[i];
        temp->next=NULL;
        cur->next=temp;
        cur=cur->next;
    }
    return result->next;
}