合并k个已排序的链表

C 解法, 执行用时: 40ms, 内存消耗: 8756KB, 提交时间: 2022-07-17

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    if(listsLen <= 1)
        return *lists;
    int allnum[2001] = {0};
    struct ListNode* curr = (struct ListNode*)malloc(sizeof(struct ListNode));
    int i;
    for(i = 0; i < listsLen; ++i){
        curr = lists[i];
        while(curr != NULL){
            allnum[curr->val + 1000]++;
            curr = curr->next;
        }
    }
    struct ListNode* out = (struct ListNode*)malloc(sizeof(struct ListNode));
    curr = out;
    for(i = 0; i < 2001; ++i){
        while(allnum[i]){
            struct ListNode* new = (struct ListNode*)malloc(sizeof(struct ListNode));
            new->val = i - 1000;
            curr->next = new;
            curr = curr->next;
            allnum[i]--;
        }
    }
    return out->next;
    // write code here
}

C 解法, 执行用时: 40ms, 内存消耗: 8812KB, 提交时间: 2022-05-19

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    if(listsLen<2)
        return lists[0];
    int note_num = 0;
    int num[2001]={0};
    struct ListNode *cur = NULL;
    struct ListNode *head = NULL;
    for(int i=0;i<listsLen;i++)
    {
        cur=lists[i];
        while(cur)
        {
            num[cur->val+1000]++;
            cur = cur->next;
            note_num++;
        }
    }
   
   
    for(int i=0;i<2001;i++)
    {
        while(num[i])
        {
            struct ListNode *new = (struct ListNode*)malloc(sizeof(struct ListNode));
            new->val = i-1000;
            new->next = NULL;
            if(head == NULL)
            {
                head = cur = new;
            }else
            {
                cur->next = new;
                cur = cur->next;
            }
            num[i]--;
        }   
    }
    return head;
}

C 解法, 执行用时: 42ms, 内存消耗: 8756KB, 提交时间: 2022-08-06

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    if(listsLen <= 1)
        return *lists;
    int allnum[2001] = {0};
    struct ListNode* curr = (struct ListNode*)malloc(sizeof(struct ListNode));
    int i;
    for(i = 0; i < listsLen; ++i){
        curr = lists[i];
        while(curr != NULL){
            allnum[curr->val + 1000]++;
            curr = curr->next;
        }
    }
    struct ListNode* out = (struct ListNode*)malloc(sizeof(struct ListNode));
    curr = out;
    for(i = 0; i < 2001; ++i){
        while(allnum[i]){
            struct ListNode* new = (struct ListNode*)malloc(sizeof(struct ListNode));
            new->val = i - 1000;
            curr->next = new;
            curr = curr->next;
            allnum[i]--;
        }
    }
    return out->next;
}

C 解法, 执行用时: 43ms, 内存消耗: 8748KB, 提交时间: 2022-05-14

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
 
/**
 *
 * @param lists ListNode类一维数组
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
static int cnt[2048] = {0};
static int val[1024*5] = {0};
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    int nums = 0;
    struct ListNode *head = NULL;
    struct ListNode *tail = NULL;
     
    for(int i = 0; i < listsLen; i++) {
        struct ListNode *tmp = lists[i];
        while(tmp != NULL) {
            cnt[tmp->val+1024] = cnt[tmp->val+1024] + 1;
            tmp = tmp->next;
            nums++;
        }
    }
     
    head = calloc(1, sizeof(struct ListNode));
    tail = head;
    for(int i = 0; i < 2048; i++) {
        if (cnt[i] == 0)
            continue;
        for(int j = cnt[i]; j > 0; j--) {
            struct ListNode *tmp = calloc(1, sizeof(struct ListNode));
            tmp->val = i-1024;
            tail->next = tmp;
            tail = tmp;
        }
    }
     
     
    memset(cnt, 0, sizeof(int)*2048);
    memset(val, 0, sizeof(int)*1024*5);
    tail = head->next;
    free(head);
    return tail;
}

C 解法, 执行用时: 43ms, 内存消耗: 8752KB, 提交时间: 2022-07-04

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    if(listsLen == 1)
		return lists[0];

    int num[2001]={0};
	struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode)), *cur;
    for(int i=0;i<listsLen;i++)
    {
        cur=lists[i];
        while(cur)
        {
			//将链表的val和数组下标对比，存在就给该数组元素赋值，多次相同的val，依次给该数组元素++1
            num[cur->val+1000]++;
            cur = cur->next;
        }
    }
    
	cur = head;
    for(int i=0;i<2001;i++)
    {
        while(num[i])
        {
            struct ListNode *new = (struct ListNode*)malloc(sizeof(struct ListNode));
            new->val = i-1000;
			
            cur->next = new;
            cur = new;
			
            num[i]--;
        }  
    }
	cur->next = NULL;
	
    return head->next;
}

详情