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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param lists ListNode类一维数组
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>

int cmp (const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
   // write code here
    // struct ListNode* p0;
    // struct ListNode* p1;
    // struct ListNode* p2;
    // struct ListNode* p3;
    // struct ListNode* phead;
    // int i, j;
    // int n = 0;
    // p0 = NULL;
    // p1 = NULL;


    // if (listsLen == 1) {
    //     return lists[0];
    // }
    // //1、将每一个链表依次串起来，得到一个更长的链表
    // for (i = 0; i < listsLen - 1; i++) {
    //     if (lists[i] != NULL) {
    //         p0 = lists[i];
    //     }
    //     p1 = lists[i + 1];

    //     if (p1 != NULL && p0 != NULL) {
    //         while (p0->next != NULL) {
    //             p0 = p0->next;
    //         }
    //         p0->next = p1;
    //     }
    // }

    // //2、计算新链表中元素的个数
    // phead = lists[0];
    // p0 = phead;

    // if (p0 == NULL || p0->next == NULL) {
    //     return p0;
    // }
    // while (p0->next != NULL) {
    //     p0 = p0->next;
    //     n++;
    // }
    // p0 = phead;//更新p0的指向


    // //3、采用冒泡排序法，重新对链表进行排序
    // for (i = 0; i < n; i++) {
    //     p0 = phead;
    //     p1 = p0;
    //     if(p0->next == NULL)
    //     {
    //         return p0;
    //     }
    //     for (j = 0; j <(n - i) ; j++) {
    //         p2 = p1->next;
    //         p3 = p2->next;

    //         if (p2->val < p1->val) 
    //         {
    //             p2->next = p1;
    //             p1->next = p3;
    //             if (p1 == phead) {
    //                 phead = p2;
    //             } else {
    //                 p0->next = p2;
    //             }
    //             p0 = p2;
    //         } 
    //         else 
    //         {
    //             p0 = p1;
    //         }
    //         p1 = p0->next;
    //     }
    // }
    // return  phead;

struct ListNode * result = malloc((sizeof(struct ListNode)));//申请一个头结点
int list[100000];//用于存储所有链表中的元素
int j = 0;//记录所有链表中的元素个数
struct ListNode* p0;
if(result == NULL)
{
    return  lists[0];
}
//第一步：将每个链表的元素保存到list[]中
for(int i = 0; i < listsLen; i++)
{
    p0 = lists[i];
    while (p0 != NULL) 
    {
        list[j] = p0->val;
        j++;
        p0 = p0->next;
    }
}
//第二步：对list数组中的元素进行排序
qsort(list, j, sizeof(int), cmp);
p0 = result;
//第三步：将list数组中的每一个元素保存到一个链表中。
for(int i = 0; i < j; i++)
{
    struct ListNode *temp = malloc(sizeof(struct ListNode));
    temp->val = list[i];
    temp->next = NULL;
    p0->next = temp;
    p0 = p0->next;
}
return result->next;

}