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

#include <stdlib.h>
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * @author Senky
 * @date 2023.04.21
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 将数据重新排列不影响链表的位置
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */

int compar(const void* p1, const void* p2)
 {
    return (  (*(int*)p1) -
              (*(int*)p2)   );
 }

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    int str_length = 0;
    int lists_index = 0;
    int str_index = 0;

    struct ListNode* head = NULL;
    struct ListNode* p = NULL;

    //整合链表
    for(lists_index = 0; lists_index < listsLen; lists_index++) //每次处理一条链表
    {
        if(lists[lists_index])//当前链表必须为非空链表
        {
            if(p) 
            {
                /*p链接并指向新非空链表的头结点*/
                p->next = lists[lists_index];
                p = lists[lists_index];
            }
            else 
            {
                /*p为空说明是第一次链接链表,将p指向第一个非空链表的头结点*/
                head = lists[lists_index];
                p = lists[lists_index];
            } 

            while(p)//仅对本条链表循环
            {
                str_length++;//计数结点数，结点数等于要申请空间的数组长度
                /*p的下一个为空并且,链表还没处理完,则退出循环,for寻找下一跳链表*/
                if(p->next == NULL && (lists_index < listsLen - 1) )
                {
                    break;
                }
                p = p->next;
            }         
            
        }
    }
        
    /*申请数组*/
    int* str = malloc(str_length*sizeof(int));  

    /*将链接后的链表数据域写入到整数数组中*/
    {
        p = head;
        while(p)
        {
            str[str_index++] = p->val;
            p = p->next;
        }
    }


    //排序整数数组,快排O(nlongn)
    qsort(str, str_length, sizeof(str[0]), compar);

    /*将排序好的数组元素写回链表的数据域*/
    {
        p = head;
        str_index = 0;
        while(p)
        {
            p->val = str[str_index++];
            p = p->next;
        }
    }

    return head;
}