C语言力扣第23题之合并K个升序序列链表。四种方法

53 阅读 0 评论 35 点赞

我是靠谱客的博主含糊航空，最近开发中收集的这篇文章主要介绍C语言力扣第23题之合并K个升序序列链表。四种方法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
输出：[1, 1, 2, 3, 4, 4, 5, 6]
解释：链表数组如下：
[
   1->4->5,
   1->3->4,
   2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10 ^ 4
0 <= lists[i].length <= 500
- 10 ^ 4 <= lists[i][j] <= 10 ^ 4
lists[i] 按升序排列
lists[i].length 的总和不超过 10 ^ 4

来源：力扣（LeetCode）
链接：https ://leetcode.cn/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：暴力排序

不管三七二十一，先把链表数组进行遍历，头尾相接组成一个链表，然后再对一个长链表进行排序。时间复杂度比较高，但有兴趣同学可以自己进行实现。

方法二：暴力求解

最简单无脑暴力，每次取出K个链表中最小的元素，不断放入结果数组中，算是对方法一的一种优化。本人采用的也是这种方法。时间复杂度也比较高。

方法三：分治法

考虑优化方法二，用分治的方法进行合并。

    将 k个链表配对并将同一对中的链表合并；
    第一轮合并以后， k 个链表被合并成了 k/2 个链表，平均长度为 2n/k，然后是 k/4个链表， k/8个链表等等；
    重复这一过程，直到我们得到了最终的有序链表

具体两两合并的方法请参考本人的另一篇博客

C语言力扣第21题之合并两个有序链表。双指针法_管二狗绝不摆烂的博客-CSDN博客

方法四：堆排序或构建二叉排序树

相关更基础概念请参照本人的另一篇博客，二叉树的链式储存

考研复习之数据结构笔记（九）树（上）（树和二叉树的概念、特征、性质及相关实例）_管二狗绝不摆烂的博客-CSDN博客

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
	struct ListNode *res = malloc(sizeof(struct ListNode));
	struct ListNode *p;
	struct ListNode *temp = NULL;
	bool IsNULL(struct ListNode **lists, int listsSize);
	res->next = NULL;
	p = res;
	while (IsNULL(lists, listsSize)) {
		int min = 10000, minindex, i;
		for (i = 0; i < listsSize; i++) {
			if (lists[i] && lists[i]->val < min) {
				minindex = i;
				min = lists[i]->val;
			}
		}
		temp = (struct ListNode *)malloc(sizeof(struct ListNode));
		temp->val = lists[minindex]->val;
		temp->next = NULL;
		p->next = temp;
		p = temp;
		lists[minindex] = lists[minindex]->next;
	}
	return res->next;
}

bool IsNULL(struct ListNode **lists, int listsSize) {
	int i;
	bool flag = false;
	for (i = 0; i < listsSize; i++) {
		flag = flag || lists[i];
	}
	return flag;
}